Submission #616361
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll x[300][300];
ll tmp[300][300],u[300],d[300];
ll inf=1e10;
ll ans=-inf;
int H,W;
int main(){
cin>>H>>W;
rep(i,H) rep(j,W) cin>>x[i][j];
rep(i,H){
ll mx=-inf;
rep(a,W){
ll now=0;
for(int b=a;b<W;b++){
now+=x[i][b];
tmp[a][b]=max(tmp[a][b]+now,now);
chmax(mx,tmp[a][b]);
}
}
u[i]=mx;
}
rep(i,H-1) chmax(u[i+1],u[i]);
rep(i,W) rep(j,W) tmp[i][j]=0;
for(int i=H-1;i>=0;i--){
ll mx=-inf;
rep(a,W){
ll now=0;
for(int b=a;b<W;b++){
now+=x[i][b];
tmp[a][b]=max(tmp[a][b]+now,now);
chmax(mx,tmp[a][b]);
}
}
d[i]=mx;
}
for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
rep(i,H-1) chmax(ans,u[i]+d[i+1]);
rep(i,H) rep(j,W) tmp[i][j]=x[i][j];
rep(i,H) rep(j,W) x[j][i]=tmp[i][j];
swap(H,W);
rep(i,300) rep(j,300) tmp[i][j]=0;
rep(i,300) u[i]=d[i]=0;
rep(i,H){
ll mx=-inf;
rep(a,W){
ll now=0;
for(int b=a;b<W;b++){
now+=x[i][b];
tmp[a][b]=max(tmp[a][b]+now,now);
chmax(mx,tmp[a][b]);
}
}
u[i]=mx;
}
rep(i,H-1) chmax(u[i+1],u[i]);
rep(i,W) rep(j,W) tmp[i][j]=0;
for(int i=H-1;i>=0;i--){
ll mx=-inf;
rep(a,W){
ll now=0;
for(int b=a;b<W;b++){
now+=x[i][b];
tmp[a][b]=max(tmp[a][b]+now,now);
chmax(mx,tmp[a][b]);
}
}
d[i]=mx;
}
for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
rep(i,H-1) chmax(ans,u[i]+d[i+1]);
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
sigma425 |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
1786 Byte |
Status |
AC |
Exec Time |
248 ms |
Memory |
2200 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 |
27 ms |
1504 KB |
sample1.txt |
AC |
26 ms |
1564 KB |
sample2.txt |
AC |
29 ms |
1560 KB |
sample3.txt |
AC |
29 ms |
1436 KB |
subtask0_0.txt |
AC |
28 ms |
1560 KB |
subtask0_1.txt |
AC |
30 ms |
1572 KB |
subtask0_10.txt |
AC |
29 ms |
1696 KB |
subtask0_11.txt |
AC |
28 ms |
1560 KB |
subtask0_12.txt |
AC |
30 ms |
1692 KB |
subtask0_13.txt |
AC |
44 ms |
1528 KB |
subtask0_14.txt |
AC |
28 ms |
1692 KB |
subtask0_2.txt |
AC |
30 ms |
1692 KB |
subtask0_3.txt |
AC |
30 ms |
1568 KB |
subtask0_4.txt |
AC |
32 ms |
1552 KB |
subtask0_5.txt |
AC |
31 ms |
1560 KB |
subtask0_6.txt |
AC |
30 ms |
1568 KB |
subtask0_7.txt |
AC |
32 ms |
1568 KB |
subtask0_8.txt |
AC |
29 ms |
1696 KB |
subtask0_9.txt |
AC |
30 ms |
1572 KB |
subtask1_0.txt |
AC |
204 ms |
2076 KB |
subtask1_1.txt |
AC |
229 ms |
2080 KB |
subtask1_10.txt |
AC |
194 ms |
2088 KB |
subtask1_11.txt |
AC |
241 ms |
2200 KB |
subtask1_12.txt |
AC |
212 ms |
2080 KB |
subtask1_13.txt |
AC |
248 ms |
2096 KB |
subtask1_14.txt |
AC |
186 ms |
2072 KB |
subtask1_2.txt |
AC |
241 ms |
2080 KB |
subtask1_3.txt |
AC |
194 ms |
2080 KB |
subtask1_4.txt |
AC |
195 ms |
2140 KB |
subtask1_5.txt |
AC |
240 ms |
2092 KB |
subtask1_6.txt |
AC |
224 ms |
2084 KB |
subtask1_7.txt |
AC |
220 ms |
2084 KB |
subtask1_8.txt |
AC |
236 ms |
2084 KB |
subtask1_9.txt |
AC |
195 ms |
2080 KB |