Submission #632337

---

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 repa(i,b,n) for(int (i)=b; (i)<(int)(n); ++(i))
#define rep(i,n) repa(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;

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

ll sum[302][302];

ll solve() {
  rep(i,H) rep(j,W) {
    if (i == 0 && j == 0) {
      sum[0][0] = B[0][0];
    }
    else if (i == 0) {
      sum[0][j] = sum[0][j-1] + B[0][j];
    }
    else if (j == 0) {
      sum[i][0] = sum[i-1][0] + B[i][0];
    }
    else {
      sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + B[i][j];
    }
  }
  // rep(i,H) {
  //   rep(j,W) {
  //     printf("%4d", B[i][j]);
  //   }
  //   puts("");
  // }
  // rep(i,H) {
  //   rep(j,W) {
  //     printf("%4d", sum[i][j]);
  //   }
  //   puts("");
  // }

  // とりあえず全部列挙してみる
  typedef vector<ll> vi;
  const ll kInf = 1LL << 62;
  vi xs_b(W+1, -kInf), xs_e(W+1, -kInf),
    ys_b(H+1, -kInf), ys_e(H+1, -kInf);
  rep(i,H) rep(j,W) repa(ii,i+1,H+1) repa(jj,j+1,W+1) {
    ll val = 0;

    if (i == 0 && j == 0) {
      val = sum[ii-1][jj-1];
    }
    else if (i == 0) {
      val = sum[ii-1][jj-1] - sum[ii-1][j-1];
    }
    else if (j == 0) {
      val = sum[ii-1][jj-1] - sum[i-1][jj-1];
    }
    else {
      val = sum[ii-1][jj-1] + sum[i-1][j-1] - sum[ii-1][j-1] - sum[i-1][jj-1];
    }

    xs_b[j] = max(xs_b[j], val);
    ys_b[i] = max(ys_b[i], val);
    xs_e[jj-1] = max(xs_e[jj-1], val);
    ys_e[ii-1] = max(ys_e[ii-1], val);
    // cout<<"----"<<endl;
    // print(val)
    // print(i)
    // print(j)
    // print(ii)
    // print(jj)
  }

  // 最大のペアを探す
  //int ans = xs_b.front();
  ll ans = -kInf;
  // for(int xb : xs_b) { print(xb) }
  // for(int xe : xs_e) { print(xe) }
  for(int i=0;i<W;i++) {
    for(int j=i+1;j<W;j++) {
      //printf("horizontal split i,j=%d,%d (%d+%d)\n", i, j, xs[i-1], xs[j-1]);
      ans = max(ans, xs_e[i] + xs_b[j]);
    }
  }
  // for(int yb : ys_b) { print(yb) }
  // for(int ye : ys_e) { print(ye) }
  for(int i=0;i<H;i++) {
    for(int j=i+1;j<H;j++) {
      //printf("vertical split i,j=%d,%d\n (%d+%d)\n", i, j, ys[i-1], ys[j-1]);
      ans = max(ans, ys_e[i] + ys_b[j]);
    }
  }

  return ans;
}

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