Submission #3553100
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define inf 100000000000000007
using namespace std;
int n,m,a[303][303],b[303][303],c[303][303],ans;
int ans1[303],ans2[303],ans3[303],ans4[303];
int d[100100];
int ask(int x){
int res=-inf,dp=-inf;
for(int i=1;i<=x;i++)
dp=max(dp+d[i],d[i]),
res=max(res,dp);
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
b[i][j]=b[i-1][j]+a[i][j];
c[i][j]=c[i][j-1]+a[i][j];
}
memset(ans1,0xcf,sizeof(ans1));
memset(ans2,0xcf,sizeof(ans2));
memset(ans3,0xcf,sizeof(ans3));
memset(ans4,0xcf,sizeof(ans4));
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--){
for(int k=1;k<=m;k++)
d[k]=b[i][k]-b[j-1][k];
ans1[i]=max(ans1[i],ask(m));
}
ans1[i]=max(ans1[i],ans1[i-1]);
// cout<<ans1[i]<<" ";
}
// puts("");
for(int i=n;i>=1;i--){
for(int j=i;j<=n;j++){
for(int k=1;k<=m;k++)
d[k]=b[j][k]-b[i-1][k];
ans2[i]=max(ans2[i],ask(m));
}
ans2[i]=max(ans2[i],ans2[i+1]);
// cout<<ans2[i]<<" ";
}
// puts("");
for(int i=1;i<=m;i++){
for(int j=i;j>=1;j--){
for(int k=1;k<=n;k++)
d[k]=c[k][i]-c[k][j-1];
ans3[i]=max(ans3[i],ask(n));
}
ans3[i]=max(ans3[i],ans3[i-1]);
// cout<<ans3[i]<<" ";
}
// puts("");
for(int i=m;i>=1;i--){
for(int j=i;j<=m;j++){
for(int k=1;k<=n;k++)
d[k]=c[k][j]-c[k][i-1];
ans4[i]=max(ans4[i],ask(n));
}
ans4[i]=max(ans4[i],ans4[i+1]);
// cout<<ans4[i]<<" ";
}
// puts("");
ans=-inf;
for(int i=1;i<m;i++)
ans=max(ans,ans1[i]+ans2[i+1]);
for(int i=1;i<n;i++)
ans=max(ans,ans3[i]+ans4[i+1]);
cout<<ans;
}
/*
2 3
5 -1 8
-1 4 -1
4 4
5 2 -3 2
3 8 -3 -10
4 5 3 2
-5 -3 3 5
3 8
-6 1 -3 -4 1 0 5 8
-8 0 -3 0 -8 -2 8 8
-8 5 -10 9 -1 8 7 3
*/
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
luogu_bot5 |
Language |
C++ (GCC 5.4.1) |
Score |
0 |
Code Size |
1861 Byte |
Status |
WA |
Exec Time |
159 ms |
Memory |
2304 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
sample0.txt, sample1.txt, sample2.txt, sample3.txt, 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 |
WA |
1 ms |
256 KB |
sample1.txt |
WA |
1 ms |
256 KB |
sample2.txt |
WA |
1 ms |
256 KB |
sample3.txt |
WA |
1 ms |
256 KB |
subtask0_0.txt |
WA |
7 ms |
640 KB |
subtask0_1.txt |
WA |
3 ms |
512 KB |
subtask0_10.txt |
WA |
3 ms |
640 KB |
subtask0_11.txt |
WA |
2 ms |
512 KB |
subtask0_12.txt |
WA |
3 ms |
640 KB |
subtask0_13.txt |
WA |
2 ms |
640 KB |
subtask0_14.txt |
WA |
2 ms |
512 KB |
subtask0_2.txt |
WA |
2 ms |
512 KB |
subtask0_3.txt |
WA |
2 ms |
640 KB |
subtask0_4.txt |
WA |
2 ms |
512 KB |
subtask0_5.txt |
WA |
3 ms |
640 KB |
subtask0_6.txt |
WA |
3 ms |
640 KB |
subtask0_7.txt |
WA |
3 ms |
512 KB |
subtask0_8.txt |
WA |
2 ms |
512 KB |
subtask0_9.txt |
WA |
2 ms |
640 KB |
subtask1_0.txt |
WA |
128 ms |
2048 KB |
subtask1_1.txt |
WA |
151 ms |
2048 KB |
subtask1_10.txt |
WA |
121 ms |
2176 KB |
subtask1_11.txt |
WA |
159 ms |
2176 KB |
subtask1_12.txt |
WA |
136 ms |
2176 KB |
subtask1_13.txt |
WA |
157 ms |
2176 KB |
subtask1_14.txt |
WA |
119 ms |
2304 KB |
subtask1_2.txt |
WA |
158 ms |
2176 KB |
subtask1_3.txt |
WA |
123 ms |
2048 KB |
subtask1_4.txt |
WA |
124 ms |
2176 KB |
subtask1_5.txt |
WA |
155 ms |
2176 KB |
subtask1_6.txt |
WA |
145 ms |
2176 KB |
subtask1_7.txt |
WA |
138 ms |
2176 KB |
subtask1_8.txt |
WA |
158 ms |
2304 KB |
subtask1_9.txt |
WA |
126 ms |
2048 KB |