Submission #632337
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;
#define repa(i,b,n) for(int (i)=b; (i)<(int)(n); ++(i))
#define rep(i,n) repa(i,0,n)
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define all(a) (a).begin(),(a).end()
#define print(var) cout<<#var":"<<(var)<<endl;
#define printkv(key,var) cout<<#key":"<<(var)<<endl;
typedef long long ll;
template <typename T>
T modpow(T base, T exp, T modulus) {
base %= modulus;
T result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >>= 1;
}
return result;
}
int H;
int W;
ll B[302][302];
ll sum[302][302];
ll solve() {
rep(i,H) rep(j,W) {
if (i == 0 && j == 0) {
sum[0][0] = B[0][0];
}
else if (i == 0) {
sum[0][j] = sum[0][j-1] + B[0][j];
}
else if (j == 0) {
sum[i][0] = sum[i-1][0] + B[i][0];
}
else {
sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + B[i][j];
}
}
// rep(i,H) {
// rep(j,W) {
// printf("%4d", B[i][j]);
// }
// puts("");
// }
// rep(i,H) {
// rep(j,W) {
// printf("%4d", sum[i][j]);
// }
// puts("");
// }
// とりあえず全部列挙してみる
typedef vector<ll> vi;
const ll kInf = 1LL << 62;
vi xs_b(W+1, -kInf), xs_e(W+1, -kInf),
ys_b(H+1, -kInf), ys_e(H+1, -kInf);
rep(i,H) rep(j,W) repa(ii,i+1,H+1) repa(jj,j+1,W+1) {
ll val = 0;
if (i == 0 && j == 0) {
val = sum[ii-1][jj-1];
}
else if (i == 0) {
val = sum[ii-1][jj-1] - sum[ii-1][j-1];
}
else if (j == 0) {
val = sum[ii-1][jj-1] - sum[i-1][jj-1];
}
else {
val = sum[ii-1][jj-1] + sum[i-1][j-1] - sum[ii-1][j-1] - sum[i-1][jj-1];
}
xs_b[j] = max(xs_b[j], val);
ys_b[i] = max(ys_b[i], val);
xs_e[jj-1] = max(xs_e[jj-1], val);
ys_e[ii-1] = max(ys_e[ii-1], val);
// cout<<"----"<<endl;
// print(val)
// print(i)
// print(j)
// print(ii)
// print(jj)
}
// 最大のペアを探す
//int ans = xs_b.front();
ll ans = -kInf;
// for(int xb : xs_b) { print(xb) }
// for(int xe : xs_e) { print(xe) }
for(int i=0;i<W;i++) {
for(int j=i+1;j<W;j++) {
//printf("horizontal split i,j=%d,%d (%d+%d)\n", i, j, xs[i-1], xs[j-1]);
ans = max(ans, xs_e[i] + xs_b[j]);
}
}
// for(int yb : ys_b) { print(yb) }
// for(int ye : ys_e) { print(ye) }
for(int i=0;i<H;i++) {
for(int j=i+1;j<H;j++) {
//printf("vertical split i,j=%d,%d\n (%d+%d)\n", i, j, ys[i-1], ys[j-1]);
ans = max(ans, ys_e[i] + ys_b[j]);
}
}
return ans;
}
int main()
{
while (cin >> H >> W) {
rep(i,H) rep(j,W) {
cin >> B[i][j];
}
cout << solve() << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
brly |
Language |
C++11 (Clang++ 3.4) |
Score |
50 |
Code Size |
3191 Byte |
Status |
TLE |
Exec Time |
2560 ms |
Memory |
2228 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
50 / 50 |
0 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask1 |
subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample0.txt |
AC |
25 ms |
924 KB |
sample1.txt |
AC |
26 ms |
804 KB |
sample2.txt |
AC |
26 ms |
800 KB |
sample3.txt |
AC |
25 ms |
924 KB |
subtask0_0.txt |
AC |
36 ms |
1032 KB |
subtask0_1.txt |
AC |
33 ms |
936 KB |
subtask0_10.txt |
AC |
35 ms |
1060 KB |
subtask0_11.txt |
AC |
33 ms |
924 KB |
subtask0_12.txt |
AC |
35 ms |
932 KB |
subtask0_13.txt |
AC |
34 ms |
936 KB |
subtask0_14.txt |
AC |
33 ms |
1048 KB |
subtask0_2.txt |
AC |
30 ms |
928 KB |
subtask0_3.txt |
AC |
35 ms |
988 KB |
subtask0_4.txt |
AC |
33 ms |
1040 KB |
subtask0_5.txt |
AC |
33 ms |
1052 KB |
subtask0_6.txt |
AC |
34 ms |
928 KB |
subtask0_7.txt |
AC |
34 ms |
976 KB |
subtask0_8.txt |
AC |
31 ms |
932 KB |
subtask0_9.txt |
AC |
34 ms |
920 KB |
subtask1_0.txt |
TLE |
2558 ms |
2008 KB |
subtask1_1.txt |
TLE |
2558 ms |
2088 KB |
subtask1_10.txt |
TLE |
2560 ms |
2072 KB |
subtask1_11.txt |
TLE |
2557 ms |
2080 KB |
subtask1_12.txt |
TLE |
2559 ms |
2088 KB |
subtask1_13.txt |
TLE |
2559 ms |
2212 KB |
subtask1_14.txt |
TLE |
2559 ms |
2212 KB |
subtask1_2.txt |
TLE |
2560 ms |
2212 KB |
subtask1_3.txt |
TLE |
2558 ms |
2088 KB |
subtask1_4.txt |
TLE |
2559 ms |
2088 KB |
subtask1_5.txt |
TLE |
2557 ms |
2208 KB |
subtask1_6.txt |
TLE |
2558 ms |
2136 KB |
subtask1_7.txt |
TLE |
2560 ms |
2084 KB |
subtask1_8.txt |
TLE |
2558 ms |
2228 KB |
subtask1_9.txt |
TLE |
2560 ms |
2072 KB |