Submission #619946

---

Source Code Expand

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll LLINF = LLONG_MAX;
const int MAX = 310;

ll b[MAX][MAX],sum[MAX][MAX];
ll upper[MAX], bottom[MAX];

void rotate90(int h,int w){
  swap(h,w);
  vector<vector<ll> > ret(h,vector<ll>(w,0));
  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      ret[y][x] = b[w-1-x][y];
    }
  }
  rep(i,h) rep(j,w) b[i][j] = ret[i][j];
}

inline ll calcSum(int x1,int y1,int x2,int y2) {
  ll ret = sum[y2][x2];
  if( y1-1 >= 0 ) ret -= sum[y1-1][x2];
  if( x1-1 >= 0 ) ret -= sum[y2][x1-1];
  if( y1-1 >= 0 && x1-1 >= 0 ) ret += sum[y1-1][x1-1];
  return ret;
}

ll calc(int h,int w) {
  rep(i,h) rep(j,w) {
    sum[i][j] = b[i][j];
    if( j-1 >= 0 ) sum[i][j] += sum[i][j-1];
    if( i-1 >= 0 ) sum[i][j] += sum[i-1][j];
    if( j-1 >= 0 && i-1 >= 0 ) sum[i][j] -= sum[i-1][j-1];
  }
  rep(i,h) upper[i] =  bottom[i] = -LLINF;
  rep(y1,h) REP(y2,y1,h) {
    ll maxi = -LLINF;
    ll mini = 0;
    rep(x,w) {
      maxi = max(maxi,calcSum(0,y1,x,y2)-mini);
      //maxi = max(maxi,calcSum(0,y1,x,y2));
      mini = min(mini,calcSum(0,y1,x,y2));
    }
    upper[y2]  = max(maxi,upper[y2]);
    bottom[y1] = max(maxi,bottom[y1]);
  }
  REP(y,1,h) upper[y] = max(upper[y],upper[y-1]);
  for(int y=h-2;y>=0;y--) bottom[y] = max(bottom[y],bottom[y+1]);
  ll maxi = -LLINF;
  rep(y,h-1) maxi = max(maxi,upper[y]+bottom[y+1]);
  return maxi;
}

void compute(int h,int w) {
  ll maxi = calc(h,w);
  rotate90(h,w);
  swap(h,w);
  maxi = max(maxi,calc(h,w));
  cout << maxi << endl;
}

int main() {
  int h,w;
  cin >> h >> w;
  rep(i,h) rep(j,w) cin >> b[i][j];
  compute(h,w);
  return 0;
}

Submission Info

Judge Result