Submission #616203
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
ll solve(vvl& d) {
int h = sz(d);
int w = sz(d[0])-1;
rep(i,h)rep(j,w) d[i][j+1] += d[i][j];
vvl s(2,vl(h, -LINF));
rep(ri,2) {
rep(l,w)rep(r,w) if (l <= r) {
ll sum = 0, mn = 0;
rep(i,h) {
sum += d[i][r+1]-d[i][l];
maxs(s[ri][i], sum-mn);
mins(mn, sum);
}
}
rep(i,h-1) maxs(s[ri][i+1], s[ri][i]);
reverse(rng(d));
}
ll res = -LINF;
rep(i,h-1) maxs(res, s[0][i]+s[1][h-2-i]);
return res;
}
int main() {
int h, w;
scanf("%d%d",&h,&w);
vvl d(h,vl(w+1));
rep(i,h)rep(j,w) scanf("%lld",&d[i][j+1]);
vvl e(w,vl(h+1));
rep(i,h)rep(j,w) e[j][i+1] = d[i][j+1];
ll ans = solve(d);
maxs(ans, solve(e));
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2016-01-23 20:19:19+0900
Task
D - 庭園
User
snuke
Language
C++11 (GCC 4.9.2)
Score
100
Code Size
2139 Byte
Status
AC
Exec Time
344 ms
Memory
2088 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&h,&w);
^
./Main.cpp:76:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,h)rep(j,w) scanf("%lld",&d[i][j+1]);
^
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
25 ms
920 KB
sample1.txt
AC
23 ms
920 KB
sample2.txt
AC
23 ms
800 KB
sample3.txt
AC
23 ms
916 KB
subtask0_0.txt
AC
26 ms
924 KB
subtask0_1.txt
AC
24 ms
928 KB
subtask0_10.txt
AC
27 ms
752 KB
subtask0_11.txt
AC
26 ms
928 KB
subtask0_12.txt
AC
27 ms
732 KB
subtask0_13.txt
AC
26 ms
924 KB
subtask0_14.txt
AC
26 ms
924 KB
subtask0_2.txt
AC
26 ms
928 KB
subtask0_3.txt
AC
26 ms
920 KB
subtask0_4.txt
AC
27 ms
800 KB
subtask0_5.txt
AC
26 ms
928 KB
subtask0_6.txt
AC
24 ms
928 KB
subtask0_7.txt
AC
26 ms
920 KB
subtask0_8.txt
AC
26 ms
796 KB
subtask0_9.txt
AC
26 ms
928 KB
subtask1_0.txt
AC
260 ms
1828 KB
subtask1_1.txt
AC
344 ms
1952 KB
subtask1_10.txt
AC
248 ms
1824 KB
subtask1_11.txt
AC
321 ms
1960 KB
subtask1_12.txt
AC
276 ms
1828 KB
subtask1_13.txt
AC
336 ms
2088 KB
subtask1_14.txt
AC
259 ms
1820 KB
subtask1_2.txt
AC
314 ms
1956 KB
subtask1_3.txt
AC
256 ms
1832 KB
subtask1_4.txt
AC
278 ms
1944 KB
subtask1_5.txt
AC
308 ms
1960 KB
subtask1_6.txt
AC
291 ms
1956 KB
subtask1_7.txt
AC
281 ms
1824 KB
subtask1_8.txt
AC
329 ms
2084 KB
subtask1_9.txt
AC
286 ms
1948 KB