Submission #618284
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define MIN(a,b) (a < b ? a : b)
#define MAX(a,b) (a > b ? a : b)
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define bitcount(b) __builtin_popcount(b)
#define GCD(a,b) (__gcd(a,b))
#define GCD3(a,b,c) (GCD(GCD(a,b), c))
#define LCM(a,b) (a/GCD(a,b)*b)
#define LCM3(a,b,c) LCM(LCM(a,b),c)
#define MOD 1000000007
template<class T> inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
typedef long long ll;
// -------------------------------------
int H, W;
int B[333][333];
ll S[333][333];
ll sum(int t, int b, int l, int r) {
ll ret = S[b-1][r-1];
if (t > 0) {
ret -= S[t-1][r-1];
}
if (l > 0) {
ret -= S[b-1][l-1];
}
if (l > 0 && t > 0) {
ret += S[t-1][l-1];
}
return ret;
}
ll dp[333][2];
int main() {
cin >> H >> W;
//if (H > 50 || W > 50) return 0;
REP(i, H) {
REP(j, W) {
cin >> S[i][j];
}
}
REP(i, H) {
REP(j, W) {
if (j > 0) S[i][j] += S[i][j-1];
}
}
REP(j, W) {
REP(i, H) {
if (i > 0) S[i][j] += S[i-1][j];
}
}
ll dp[333][2];
ll tb[333][333];
FOR(t, 0, H) {
FOR(b, t+1, H+1) {
FILL(dp, 0xf3);
FOR(i, 0, W+1) {
dp[i+1][0] = MAX(dp[i][0], dp[i][1]);
dp[i+1][1] = MAX(0, dp[i][1]) + sum(t, b, i, i+1);
}
tb[t][b] = MAX(dp[W][0], dp[W][1]);
}
}
ll lr[333][333];
FOR(l, 0, W) {
FOR(r, l+1, W+1) {
FILL(dp, 0xf3);
FOR(i, 0, H+1) {
dp[i+1][0] = MAX(dp[i][0], dp[i][1]);
dp[i+1][1] = MAX(0, dp[i][1]) + sum(i, i+1, l, r);
}
lr[l][r] = MAX(dp[H][0], dp[H][1]);
}
}
ll ans = (ll) -MOD * MOD;
FOR(y, 1, H) {
ll mt = (ll) -MOD * MOD;
FOR(y1, 0, y) FOR(y2, y1+1, y+1) {
amax(mt, tb[y1][y2]);
}
ll mb = (ll) -MOD * MOD;
FOR(y1, y, H) FOR(y2, y1+1, H+1) {
amax(mb, tb[y1][y2]);
}
amax(ans, mt + mb);
}
FOR(x, 1, W) {
ll ml = (ll) -MOD * MOD;
FOR(x1, 0, x) FOR(x2, x1+1, x+1) {
amax(ml, lr[x1][x2]);
}
ll mr = (ll) -MOD * MOD;
FOR(x1, x, W) FOR(x2, x1+1, W+1) {
amax(mr, lr[x1][x2]);
}
//_P("%d->%lld,%lld\n", x, ml, mr);
amax(ans, ml + mr);
}
cout << ans << '\n';
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
shiratty8 |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
3053 Byte |
Status |
AC |
Exec Time |
402 ms |
Memory |
2984 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 |
30 ms |
764 KB |
sample1.txt |
AC |
26 ms |
800 KB |
sample2.txt |
AC |
26 ms |
776 KB |
sample3.txt |
AC |
26 ms |
808 KB |
subtask0_0.txt |
AC |
29 ms |
1108 KB |
subtask0_1.txt |
AC |
29 ms |
1176 KB |
subtask0_10.txt |
AC |
30 ms |
1184 KB |
subtask0_11.txt |
AC |
29 ms |
1060 KB |
subtask0_12.txt |
AC |
29 ms |
1180 KB |
subtask0_13.txt |
AC |
30 ms |
1168 KB |
subtask0_14.txt |
AC |
28 ms |
1180 KB |
subtask0_2.txt |
AC |
30 ms |
1120 KB |
subtask0_3.txt |
AC |
31 ms |
1056 KB |
subtask0_4.txt |
AC |
30 ms |
1056 KB |
subtask0_5.txt |
AC |
30 ms |
1304 KB |
subtask0_6.txt |
AC |
29 ms |
1184 KB |
subtask0_7.txt |
AC |
32 ms |
1180 KB |
subtask0_8.txt |
AC |
30 ms |
1064 KB |
subtask0_9.txt |
AC |
29 ms |
1100 KB |
subtask1_0.txt |
AC |
324 ms |
2724 KB |
subtask1_1.txt |
AC |
365 ms |
2912 KB |
subtask1_10.txt |
AC |
305 ms |
2732 KB |
subtask1_11.txt |
AC |
394 ms |
2984 KB |
subtask1_12.txt |
AC |
341 ms |
2848 KB |
subtask1_13.txt |
AC |
391 ms |
2976 KB |
subtask1_14.txt |
AC |
308 ms |
2856 KB |
subtask1_2.txt |
AC |
387 ms |
2976 KB |
subtask1_3.txt |
AC |
313 ms |
2848 KB |
subtask1_4.txt |
AC |
320 ms |
2852 KB |
subtask1_5.txt |
AC |
382 ms |
2976 KB |
subtask1_6.txt |
AC |
358 ms |
2848 KB |
subtask1_7.txt |
AC |
343 ms |
2864 KB |
subtask1_8.txt |
AC |
402 ms |
2980 KB |
subtask1_9.txt |
AC |
328 ms |
2840 KB |