Submission #2528223
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;
using vector2D = vector< vector<ll> >;
const long long int INF = 1LL << 60;
vector2D rotate(vector2D board) {
int N = board.size(), M = board[0].size();
vector2D ret(M, vector<ll>(N));
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
ret[j][i] = board[i][j];
}
}
return ret;
}
long long int solve(vector2D board) {
int N = board.size(), M = board[0].size();
vector2D sum(N, vector<ll>(M+1));
vector<ll> left(M+1, -INF), right(M+1, -INF);
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
sum[i][j+1] = sum[i][j] + board[i][j];
}
}
for(int l=0; l<M; l++) {
for(int r=l+1; r<=M; r++) {
ll mi = 0, ma = -INF, s = 0;
for(int h=0; h<N; h++) {
ll val = sum[h][r] - sum[h][l] + s;
ma = max(ma, val - mi);
mi = min(mi, val);
s = val;
}
for(int i=r; i<=M; i++) {
left[i] = max(left[i], ma);
}
for(int i=0; i<=l; i++) {
right[i] = max(right[i], ma);
}
}
}
ll ret = -INF;
for(int i=0; i<=M; i++) {
ret = max(ret, left[i] + right[i]);
}
return ret;
}
int main() {
int H, W; scanf("%d%d", &H, &W);
vector2D board(H, vector<ll>(W));
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
scanf("%lld", &board[i][j]);
}
}
long long int ans = -INF;
ans = max(ans, solve(board));
board = rotate(board);
ans = max(ans, solve(board));
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time
2018-05-19 15:50:21+0900
Task
D - 庭園
User
tsutaj
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1821 Byte
Status
AC
Exec Time
102 ms
Memory
2192 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:58:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int H, W; scanf("%d%d", &H, &W);
^
./Main.cpp:62:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &board[i][j]);
^
Judge Result
Set Name
Sample
Subtask1
All
Score / Max Score
0 / 0
50 / 50
50 / 50
Status
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
sample0.txt, sample1.txt, sample2.txt, sample3.txt, 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
1 ms
256 KB
sample1.txt
AC
1 ms
256 KB
sample2.txt
AC
1 ms
256 KB
sample3.txt
AC
1 ms
256 KB
subtask0_0.txt
AC
2 ms
256 KB
subtask0_1.txt
AC
2 ms
256 KB
subtask0_10.txt
AC
2 ms
256 KB
subtask0_11.txt
AC
2 ms
256 KB
subtask0_12.txt
AC
2 ms
256 KB
subtask0_13.txt
AC
2 ms
256 KB
subtask0_14.txt
AC
2 ms
256 KB
subtask0_2.txt
AC
2 ms
256 KB
subtask0_3.txt
AC
2 ms
256 KB
subtask0_4.txt
AC
2 ms
256 KB
subtask0_5.txt
AC
2 ms
256 KB
subtask0_6.txt
AC
2 ms
256 KB
subtask0_7.txt
AC
2 ms
256 KB
subtask0_8.txt
AC
2 ms
256 KB
subtask0_9.txt
AC
2 ms
256 KB
subtask1_0.txt
AC
77 ms
1920 KB
subtask1_1.txt
AC
102 ms
2048 KB
subtask1_10.txt
AC
72 ms
1792 KB
subtask1_11.txt
AC
94 ms
2192 KB
subtask1_12.txt
AC
81 ms
1936 KB
subtask1_13.txt
AC
100 ms
2176 KB
subtask1_14.txt
AC
76 ms
1952 KB
subtask1_2.txt
AC
92 ms
2076 KB
subtask1_3.txt
AC
74 ms
1920 KB
subtask1_4.txt
AC
81 ms
1920 KB
subtask1_5.txt
AC
90 ms
2084 KB
subtask1_6.txt
AC
86 ms
2048 KB
subtask1_7.txt
AC
82 ms
1932 KB
subtask1_8.txt
AC
97 ms
2176 KB
subtask1_9.txt
AC
83 ms
2036 KB