#include <bits/stdc++.h>
using namespace std;
#define dout if(false) cout
int lookup(vector<vector<int>>& prefixSumGrid, int x, int y) {
dout << "lookup(" << x << ", " << y << ")" << endl;
if (x < 0 || y < 0) {
dout << " = 0\n";
return 0;
}
dout << " = " << prefixSumGrid[y][x] << "\n";
return prefixSumGrid[y][x];
return 1;
}
signed main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
vector<vector<int>> verticalPrefixSum(n, vector<int>(m));
int originalCost = 0;
int in;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> in;
grid[i][j] = 2 * in - 1;
originalCost += in;
dout << originalCost << " ";
}
}
dout << endl;
for (int j = 0; j < m; j++) {
verticalPrefixSum[0][j] = grid[0][j];
for (int i = 1; i < n; i++) {
verticalPrefixSum[i][j] = verticalPrefixSum[i-1][j] + grid[i][j];
}
}
for (auto a : verticalPrefixSum) {
for (auto b : a) {
dout << b << " " ;
}
dout << endl;
}
int best = -1;
for (int bottom = -1; bottom < n; bottom++) {
for (int top = bottom + 1; top < n; top++) {
int right = 0;
int result = 0;
while (right < m) {
result += lookup(verticalPrefixSum, right, top) - lookup(verticalPrefixSum, right, bottom);
right++;
result = max(result, 0);
best = max(result, best);
}
}
}
cout << originalCost-best << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
504 KB |
Output is correct |
2 |
Correct |
6 ms |
504 KB |
Output is correct |
3 |
Correct |
6 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
12524 KB |
Output is correct |
2 |
Correct |
273 ms |
14012 KB |
Output is correct |
3 |
Correct |
273 ms |
14252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
2796 KB |
Output is correct |
2 |
Correct |
58 ms |
2724 KB |
Output is correct |
3 |
Correct |
56 ms |
2672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
376 KB |
Output is correct |
2 |
Correct |
11 ms |
548 KB |
Output is correct |
3 |
Correct |
10 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
281 ms |
6804 KB |
Output is correct |
2 |
Correct |
281 ms |
7736 KB |
Output is correct |
3 |
Correct |
281 ms |
7800 KB |
Output is correct |