Submission #618281


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];

ll search(int T, int B, int L, int R) {
  ll ret = (ll) -MOD * MOD;
  FOR(t, T, B) {
    FOR(b, t+1, B+1) {
      FILL(dp, 0xf3);

      FOR(i, L, R+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);
      }
      amax(ret, dp[R][0]);
      amax(ret, dp[R][1]);
    }
  }
  //_P("%d,%d,%d,%d -> %lld\n", T, B, L, R, ret);
  return ret;
}

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 3469 Byte
Status AC
Exec Time 393 ms
Memory 2976 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 4
AC × 15
AC × 30
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 24 ms 924 KB
sample1.txt AC 23 ms 804 KB
sample2.txt AC 25 ms 928 KB
sample3.txt AC 23 ms 796 KB
subtask0_0.txt AC 30 ms 1180 KB
subtask0_1.txt AC 30 ms 1152 KB
subtask0_10.txt AC 31 ms 1176 KB
subtask0_11.txt AC 27 ms 1056 KB
subtask0_12.txt AC 29 ms 1188 KB
subtask0_13.txt AC 26 ms 1184 KB
subtask0_14.txt AC 26 ms 1184 KB
subtask0_2.txt AC 28 ms 1184 KB
subtask0_3.txt AC 29 ms 1176 KB
subtask0_4.txt AC 28 ms 1180 KB
subtask0_5.txt AC 29 ms 1180 KB
subtask0_6.txt AC 28 ms 1056 KB
subtask0_7.txt AC 27 ms 1100 KB
subtask0_8.txt AC 27 ms 1068 KB
subtask0_9.txt AC 28 ms 1184 KB
subtask1_0.txt AC 333 ms 2736 KB
subtask1_1.txt AC 364 ms 2860 KB
subtask1_10.txt AC 302 ms 2788 KB
subtask1_11.txt AC 391 ms 2896 KB
subtask1_12.txt AC 340 ms 2844 KB
subtask1_13.txt AC 389 ms 2976 KB
subtask1_14.txt AC 304 ms 2848 KB
subtask1_2.txt AC 387 ms 2972 KB
subtask1_3.txt AC 312 ms 2848 KB
subtask1_4.txt AC 321 ms 2808 KB
subtask1_5.txt AC 383 ms 2972 KB
subtask1_6.txt AC 359 ms 2844 KB
subtask1_7.txt AC 347 ms 2848 KB
subtask1_8.txt AC 393 ms 2972 KB
subtask1_9.txt AC 330 ms 2844 KB