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

Submission #632337

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

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

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 0 / 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 25 ms 924 KB
sample1.txt AC 26 ms 804 KB
sample2.txt AC 26 ms 800 KB
sample3.txt AC 25 ms 924 KB
subtask0_0.txt AC 36 ms 1032 KB
subtask0_1.txt AC 33 ms 936 KB
subtask0_10.txt AC 35 ms 1060 KB
subtask0_11.txt AC 33 ms 924 KB
subtask0_12.txt AC 35 ms 932 KB
subtask0_13.txt AC 34 ms 936 KB
subtask0_14.txt AC 33 ms 1048 KB
subtask0_2.txt AC 30 ms 928 KB
subtask0_3.txt AC 35 ms 988 KB
subtask0_4.txt AC 33 ms 1040 KB
subtask0_5.txt AC 33 ms 1052 KB
subtask0_6.txt AC 34 ms 928 KB
subtask0_7.txt AC 34 ms 976 KB
subtask0_8.txt AC 31 ms 932 KB
subtask0_9.txt AC 34 ms 920 KB
subtask1_0.txt TLE
subtask1_1.txt TLE
subtask1_10.txt TLE
subtask1_11.txt TLE
subtask1_12.txt TLE
subtask1_13.txt TLE
subtask1_14.txt TLE
subtask1_2.txt TLE
subtask1_3.txt TLE
subtask1_4.txt TLE
subtask1_5.txt TLE
subtask1_6.txt TLE
subtask1_7.txt TLE
subtask1_8.txt TLE
subtask1_9.txt TLE