Submission #637939

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define REP(i,b,n) for(int (i)=b; (i)<(int)(n); ++(i))
#define rep(i,n) REP(i,0,n)
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define all(a) (a).begin(),(a).end()
#define print(var) cout<<#var":"<<(var)<<endl;
#define printkv(key,var) cout<<#key":"<<(var)<<endl;
#define updatemax(dst,src) dst=max(dst,src);
#define updatemin(dst,src) dst=min(dst,src);

typedef long long ll;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
  if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

int H;
int W;
ll B[302][302];
const ll kInf = 1LL << 62;
typedef vector<ll> vll;
typedef vector<vll> mll;

ll sub_solve(const mll &src, const ll kH, const ll kW) {
  ll ret = -kInf;

  mll rows(kH, vll(kW, 0));
  rep(i,kH) {
    ll t = 0;
    rep(j,kW) {
      t += src[i][j];
      rows[i][j] = t;
    }
  }

  vll begin(kW, -kInf), end(kW, -kInf);

  rep(x0,kW) REP(x1,x0,kW) {
    vll vc0(kH, 0);
    rep(i,kH) {
      vc0[i] = rows[i][x1] - (x0 > 0 ? rows[i][x0-1] : 0);
    }
    vll vc1(kH, 0);
    rep(i,kH) {
      vc1[i] = vc0[i];
      if (i) {
        vc1[i] += vc1[i-1];
      }
    }
    // puts("----");
    // for (ll l : vc1) { printkv(vc1, l) }
    ll mx = -kInf;
    for(int i=kH-1; i>=0; i--) {
      updatemax(mx, vc1[i]);
      ll d = (i > 0 ? vc1[i-1] : 0);
      ll val = mx - d;
      updatemax(begin[x0], val);
      updatemax(end[x1], val);
    }
  }

  // for(ll l : begin) { printkv(begin,l) }
  // for(ll l : end) { printkv(end,l) }

  rep(x0,kW) REP(x1,x0+1,kW) {
    updatemax(ret, end[x0] + begin[x1]);
  }

  return ret;
}

ll solve() {
  mll A0(H, vll(W)), A1(W, vll(H));

  rep(i,H) rep(j,W) {
    A0[i][j] = B[i][j];
    A1[j][i] = B[i][j];
  }

  // rep(i,W) {
  //   rep(j,H) printf("%3lld", A1[i][j]);
  //   puts("");
  // }

  return max(sub_solve(A0, H, W), sub_solve(A1, W, H));
  //return sub_solve(A1, W, H);
  //return sub_solve(A0, H, W);
}

int main()
{
  while (cin >> H >> W) {
    rep(i,H) rep(j,W) {
      cin >> B[i][j];
    }
    cout << solve() << endl;
  }
  return 0;
}

Submission Info

Judge Result