Submission #1864935
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF 1e16
ll h,w;
ll b[303][303],c[303][303];
ll sum[303][303];
ll l[303],r[303];
ll solve(){
rep(i,h)rep(j,w){
sum[i+1][j+1]=b[i][j];
}
rep(i,h+1)rep(j,w)sum[i][j+1]+=sum[i][j];
rep(i,h)rep(j,w+1)sum[i+1][j]+=sum[i][j];
rep(i,w+1)l[i]=-INF;
l[0]=0;
rep(lb,h)repl(ub,lb,h){
vector<ll> a;
rep(j,w)a.push_back(sum[ub+1][j+1]-sum[ub+1][j]-sum[lb][j+1]+sum[lb][j]);
ll s=0;
rep(j,w){
s+=a[j];
if(s<a[j])s=a[j];
maxch(l[j+1],s);
}
}
repl(i,1,w)maxch(l[i+1],l[i]);
rep(i,w+1)r[i]=-INF;
r[0]=0;
rep(lb,h)repl(ub,lb,h){
vector<ll> a;
rep(j,w)a.push_back(sum[ub+1][w-j]-sum[ub+1][w-j-1]-sum[lb][w-j]+sum[lb][w-j-1]);
ll s=0;
rep(j,w){
s+=a[j];
if(s<a[j])s=a[j];
maxch(r[j+1],s);
}
}
repl(j,1,w)maxch(r[j+1],r[j]);
ll res=-INF;
repl(j,1,w)maxch(res,l[j]+r[w-j]);
return res;
}
int main(){
cin>>h>>w;
rep(i,h)rep(j,w)cin>>b[i][j];
ll resa=solve();
rep(i,h)rep(j,w)c[j][i]=b[i][j];
memcpy(b,c,sizeof(c));
swap(h,w);
ll resb=solve();
cout<<max(resa,resb)<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1802 Byte |
Status |
AC |
Exec Time |
380 ms |
Memory |
2432 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 |
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 |
AC |
2 ms |
1024 KB |
sample1.txt |
AC |
2 ms |
1024 KB |
sample2.txt |
AC |
2 ms |
1024 KB |
sample3.txt |
AC |
2 ms |
1024 KB |
subtask0_0.txt |
AC |
5 ms |
1152 KB |
subtask0_1.txt |
AC |
6 ms |
1152 KB |
subtask0_10.txt |
AC |
6 ms |
1152 KB |
subtask0_11.txt |
AC |
5 ms |
1152 KB |
subtask0_12.txt |
AC |
6 ms |
1152 KB |
subtask0_13.txt |
AC |
5 ms |
1152 KB |
subtask0_14.txt |
AC |
5 ms |
1152 KB |
subtask0_2.txt |
AC |
5 ms |
1152 KB |
subtask0_3.txt |
AC |
5 ms |
1152 KB |
subtask0_4.txt |
AC |
5 ms |
1152 KB |
subtask0_5.txt |
AC |
6 ms |
1152 KB |
subtask0_6.txt |
AC |
6 ms |
1152 KB |
subtask0_7.txt |
AC |
6 ms |
1152 KB |
subtask0_8.txt |
AC |
5 ms |
1152 KB |
subtask0_9.txt |
AC |
5 ms |
1152 KB |
subtask1_0.txt |
AC |
302 ms |
2304 KB |
subtask1_1.txt |
AC |
339 ms |
2432 KB |
subtask1_10.txt |
AC |
284 ms |
2176 KB |
subtask1_11.txt |
AC |
375 ms |
2432 KB |
subtask1_12.txt |
AC |
326 ms |
2304 KB |
subtask1_13.txt |
AC |
379 ms |
2432 KB |
subtask1_14.txt |
AC |
296 ms |
2176 KB |
subtask1_2.txt |
AC |
370 ms |
2304 KB |
subtask1_3.txt |
AC |
305 ms |
2304 KB |
subtask1_4.txt |
AC |
319 ms |
2304 KB |
subtask1_5.txt |
AC |
367 ms |
2304 KB |
subtask1_6.txt |
AC |
343 ms |
2304 KB |
subtask1_7.txt |
AC |
328 ms |
2304 KB |
subtask1_8.txt |
AC |
380 ms |
2432 KB |
subtask1_9.txt |
AC |
314 ms |
2304 KB |