Submission #616203


Source Code Expand

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}

const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

ll solve(vvl& d) {
  int h = sz(d);
  int w = sz(d[0])-1;
  rep(i,h)rep(j,w) d[i][j+1] += d[i][j];
  vvl s(2,vl(h, -LINF));
  rep(ri,2) {
    rep(l,w)rep(r,w) if (l <= r) {
      ll sum = 0, mn = 0;
      rep(i,h) {
        sum += d[i][r+1]-d[i][l];
        maxs(s[ri][i], sum-mn);
        mins(mn, sum);
      }
    }
    rep(i,h-1) maxs(s[ri][i+1], s[ri][i]);
    reverse(rng(d));
  }
  ll res = -LINF;
  rep(i,h-1) maxs(res, s[0][i]+s[1][h-2-i]);
  return res;
}


int main() {
  int h, w;
  scanf("%d%d",&h,&w);
  vvl d(h,vl(w+1));
  rep(i,h)rep(j,w) scanf("%lld",&d[i][j+1]);
  vvl e(w,vl(h+1));
  rep(i,h)rep(j,w) e[j][i+1] = d[i][j+1];
  ll ans = solve(d);
  maxs(ans, solve(e));
  cout<<ans<<endl;
  return 0;
}




Submission Info

Submission Time
Task D - 庭園
User snuke
Language C++11 (GCC 4.9.2)
Score 100
Code Size 2139 Byte
Status AC
Exec Time 344 ms
Memory 2088 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&h,&w);
                      ^
./Main.cpp:76:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   rep(i,h)rep(j,w) scanf("%lld",&d[i][j+1]);
                                            ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 4
AC × 15
AC × 30
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask1 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 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
Case Name Status Exec Time Memory
sample0.txt AC 25 ms 920 KB
sample1.txt AC 23 ms 920 KB
sample2.txt AC 23 ms 800 KB
sample3.txt AC 23 ms 916 KB
subtask0_0.txt AC 26 ms 924 KB
subtask0_1.txt AC 24 ms 928 KB
subtask0_10.txt AC 27 ms 752 KB
subtask0_11.txt AC 26 ms 928 KB
subtask0_12.txt AC 27 ms 732 KB
subtask0_13.txt AC 26 ms 924 KB
subtask0_14.txt AC 26 ms 924 KB
subtask0_2.txt AC 26 ms 928 KB
subtask0_3.txt AC 26 ms 920 KB
subtask0_4.txt AC 27 ms 800 KB
subtask0_5.txt AC 26 ms 928 KB
subtask0_6.txt AC 24 ms 928 KB
subtask0_7.txt AC 26 ms 920 KB
subtask0_8.txt AC 26 ms 796 KB
subtask0_9.txt AC 26 ms 928 KB
subtask1_0.txt AC 260 ms 1828 KB
subtask1_1.txt AC 344 ms 1952 KB
subtask1_10.txt AC 248 ms 1824 KB
subtask1_11.txt AC 321 ms 1960 KB
subtask1_12.txt AC 276 ms 1828 KB
subtask1_13.txt AC 336 ms 2088 KB
subtask1_14.txt AC 259 ms 1820 KB
subtask1_2.txt AC 314 ms 1956 KB
subtask1_3.txt AC 256 ms 1832 KB
subtask1_4.txt AC 278 ms 1944 KB
subtask1_5.txt AC 308 ms 1960 KB
subtask1_6.txt AC 291 ms 1956 KB
subtask1_7.txt AC 281 ms 1824 KB
subtask1_8.txt AC 329 ms 2084 KB
subtask1_9.txt AC 286 ms 1948 KB