Submission #615995
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);
}
}
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:11:09+0900
Task
D - 庭園
User
snuke
Language
C++11 (GCC 4.9.2)
Score
0
Code Size
2095 Byte
Status
WA
Exec Time
345 ms
Memory
2084 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:73: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:75: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
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
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
916 KB
sample1.txt
AC
24 ms
920 KB
sample2.txt
AC
25 ms
800 KB
sample3.txt
AC
26 ms
800 KB
subtask0_0.txt
WA
27 ms
916 KB
subtask0_1.txt
WA
27 ms
916 KB
subtask0_10.txt
WA
27 ms
800 KB
subtask0_11.txt
WA
27 ms
912 KB
subtask0_12.txt
AC
26 ms
796 KB
subtask0_13.txt
WA
27 ms
804 KB
subtask0_14.txt
AC
27 ms
920 KB
subtask0_2.txt
AC
27 ms
796 KB
subtask0_3.txt
WA
28 ms
796 KB
subtask0_4.txt
AC
25 ms
800 KB
subtask0_5.txt
WA
24 ms
928 KB
subtask0_6.txt
WA
25 ms
808 KB
subtask0_7.txt
AC
25 ms
804 KB
subtask0_8.txt
WA
27 ms
912 KB
subtask0_9.txt
AC
26 ms
912 KB
subtask1_0.txt
WA
265 ms
1884 KB
subtask1_1.txt
WA
345 ms
1956 KB
subtask1_10.txt
WA
246 ms
1820 KB
subtask1_11.txt
WA
319 ms
1956 KB
subtask1_12.txt
AC
276 ms
1820 KB
subtask1_13.txt
WA
336 ms
2084 KB
subtask1_14.txt
AC
261 ms
1836 KB
subtask1_2.txt
AC
317 ms
2008 KB
subtask1_3.txt
WA
256 ms
1824 KB
subtask1_4.txt
AC
281 ms
1888 KB
subtask1_5.txt
WA
307 ms
1960 KB
subtask1_6.txt
WA
293 ms
1880 KB
subtask1_7.txt
AC
281 ms
1948 KB
subtask1_8.txt
WA
333 ms
2084 KB
subtask1_9.txt
WA
284 ms
1948 KB