第2回 ドワンゴからの挑戦状 予選

Submission #637939

Source codeソースコード

#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

Task問題 D - 庭園
User nameユーザ名 brly
Created time投稿日時
Language言語 C++11 (Clang++ 3.4)
Status状態 AC
Score得点 100
Source lengthソースコード長 2633 Byte
File nameファイル名
Exec time実行時間 404 ms
Memory usageメモリ使用量 3516 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample0.txt,sample1.txt,sample2.txt,sample3.txt
Subtask1 50 / 50 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 50 / 50 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample0.txt AC 106 ms 932 KB
sample1.txt AC 28 ms 1044 KB
sample2.txt AC 27 ms 1040 KB
sample3.txt AC 26 ms 1040 KB
subtask0_0.txt AC 30 ms 1168 KB
subtask0_1.txt AC 30 ms 1076 KB
subtask0_10.txt AC 31 ms 1172 KB
subtask0_11.txt AC 30 ms 1176 KB
subtask0_12.txt AC 28 ms 1044 KB
subtask0_13.txt AC 30 ms 1080 KB
subtask0_14.txt AC 28 ms 1168 KB
subtask0_2.txt AC 30 ms 1076 KB
subtask0_3.txt AC 29 ms 1080 KB
subtask0_4.txt AC 30 ms 1168 KB
subtask0_5.txt AC 31 ms 1076 KB
subtask0_6.txt AC 34 ms 1176 KB
subtask0_7.txt AC 30 ms 1176 KB
subtask0_8.txt AC 30 ms 1076 KB
subtask0_9.txt AC 30 ms 1172 KB
subtask1_0.txt AC 329 ms 3120 KB
subtask1_1.txt AC 396 ms 3292 KB
subtask1_10.txt AC 311 ms 3128 KB
subtask1_11.txt AC 404 ms 3384 KB
subtask1_12.txt AC 346 ms 3252 KB
subtask1_13.txt AC 400 ms 3508 KB
subtask1_14.txt AC 313 ms 3352 KB
subtask1_2.txt AC 396 ms 3388 KB
subtask1_3.txt AC 324 ms 3228 KB
subtask1_4.txt AC 326 ms 3256 KB
subtask1_5.txt AC 391 ms 3396 KB
subtask1_6.txt AC 374 ms 3416 KB
subtask1_7.txt AC 354 ms 3252 KB
subtask1_8.txt AC 399 ms 3516 KB
subtask1_9.txt AC 359 ms 3256 KB