Submission #619945
Source Code Expand
#include<bits/stdc++.h>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
typedef long long ll;
const ll LLINF = LLONG_MAX;
const int MAX = 310;
ll b[MAX][MAX],sum[MAX][MAX];
ll upper[MAX], bottom[MAX];
void rotate90(int h,int w){
swap(h,w);
vector<vector<ll> > ret(h,vector<ll>(w,0));
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
ret[y][x] = b[w-1-x][y];
}
}
rep(i,h) rep(j,w) b[i][j] = ret[i][j];
}
inline ll calcSum(int x1,int y1,int x2,int y2) {
ll ret = sum[y2][x2];
if( y1-1 >= 0 ) ret -= sum[y1-1][x2];
if( x1-1 >= 0 ) ret -= sum[y2][x1-1];
if( y1-1 >= 0 && x1-1 >= 0 ) ret += sum[y1-1][x1-1];
return ret;
}
ll calc(int h,int w) {
rep(i,h) rep(j,w) {
sum[i][j] = b[i][j];
if( j-1 >= 0 ) sum[i][j] += sum[i][j-1];
if( i-1 >= 0 ) sum[i][j] += sum[i-1][j];
if( j-1 >= 0 && i-1 >= 0 ) sum[i][j] -= sum[i-1][j-1];
}
rep(i,h) upper[i] = bottom[i] = -LLINF;
rep(y1,h) REP(y2,y1,h) {
ll maxi = -LLINF;
ll mini = 0;
rep(x,w) {
maxi = max(maxi,calcSum(0,y1,x,y2)-mini);
maxi = max(maxi,calcSum(0,y1,x,y2));
mini = min(mini,calcSum(0,y1,x,y2));
}
upper[y2] = max(maxi,upper[y2]);
bottom[y1] = max(maxi,bottom[y1]);
}
REP(y,1,h) upper[y] = max(upper[y],upper[y-1]);
for(int y=h-2;y>=0;y--) bottom[y] = max(bottom[y],bottom[y+1]);
ll maxi = -LLINF;
rep(y,h-1) maxi = max(maxi,upper[y]+bottom[y+1]);
return maxi;
}
void compute(int h,int w) {
ll maxi = calc(h,w);
rotate90(h,w);
swap(h,w);
maxi = max(maxi,calc(h,w));
cout << maxi << endl;
}
int main() {
int h,w;
cin >> h >> w;
rep(i,h) rep(j,w) cin >> b[i][j];
compute(h,w);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
KasumiTakamiya |
Language |
C++ (GCC 4.9.2) |
Score |
100 |
Code Size |
1787 Byte |
Status |
AC |
Exec Time |
172 ms |
Memory |
2732 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
50 / 50 |
50 / 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 |
26 ms |
736 KB |
sample1.txt |
AC |
25 ms |
800 KB |
sample2.txt |
AC |
26 ms |
808 KB |
sample3.txt |
AC |
26 ms |
808 KB |
subtask0_0.txt |
AC |
26 ms |
936 KB |
subtask0_1.txt |
AC |
28 ms |
1060 KB |
subtask0_10.txt |
AC |
28 ms |
1056 KB |
subtask0_11.txt |
AC |
27 ms |
936 KB |
subtask0_12.txt |
AC |
28 ms |
1180 KB |
subtask0_13.txt |
AC |
26 ms |
1060 KB |
subtask0_14.txt |
AC |
28 ms |
1060 KB |
subtask0_2.txt |
AC |
30 ms |
932 KB |
subtask0_3.txt |
AC |
28 ms |
940 KB |
subtask0_4.txt |
AC |
28 ms |
1184 KB |
subtask0_5.txt |
AC |
28 ms |
1056 KB |
subtask0_6.txt |
AC |
28 ms |
936 KB |
subtask0_7.txt |
AC |
33 ms |
1004 KB |
subtask0_8.txt |
AC |
27 ms |
928 KB |
subtask0_9.txt |
AC |
28 ms |
1060 KB |
subtask1_0.txt |
AC |
147 ms |
2608 KB |
subtask1_1.txt |
AC |
164 ms |
2720 KB |
subtask1_10.txt |
AC |
142 ms |
2468 KB |
subtask1_11.txt |
AC |
172 ms |
2720 KB |
subtask1_12.txt |
AC |
152 ms |
2588 KB |
subtask1_13.txt |
AC |
162 ms |
2732 KB |
subtask1_14.txt |
AC |
123 ms |
2596 KB |
subtask1_2.txt |
AC |
170 ms |
2724 KB |
subtask1_3.txt |
AC |
136 ms |
2596 KB |
subtask1_4.txt |
AC |
130 ms |
2588 KB |
subtask1_5.txt |
AC |
172 ms |
2720 KB |
subtask1_6.txt |
AC |
163 ms |
2712 KB |
subtask1_7.txt |
AC |
157 ms |
2592 KB |
subtask1_8.txt |
AC |
162 ms |
2720 KB |
subtask1_9.txt |
AC |
130 ms |
2596 KB |