Farming
Time limit: 1 second
Memory limit: 256 megabytes
There is a farm in the shape of an \(N \cdot N\) grid. The cell \((i, j)\) has crops of value \(G_{i,j}\). If \(G_{i,j}\) is negative then the crops are rotten.
Abdulaziz and Almothana want to harvest \(K \cdot K\) sub-grids of crops each. Obviously, the sub-grids may not intersect. Can you help Abdulaziz and Almothana select them optimally so that the total sum of values for the sub-grids is maximized.
Note 1: A sub-grid is a sub-rectangle of the main grid.
Note 2: Two \(K \cdot K\) sub-grids will be selected such that they don’t interset.
Input
The first line contains \(N\) and \(K\). \((1 \leq 2*K \leq N \leq 500)\)
The next \(N\) lines contain \(N\) numbers each, the values of the crops. \((-10^9 \leq G_{i, j} \leq 10^9)\)
Output
Print the maximum total sum of the sub-grids.
Scoring
| Group | Constraints | Points |
|---|---|---|
| \(1\) | \(N = 2\) | \(25\) |
| \(2\) | All values of \(G_{i,j}\) are equal | \(25\) |
| \(3\) | \(N = 10\) | \(25\) |
| \(4\) | — | \(25\) |
Examples
Input
2 1
3 1
2 4
Output
7
Input
5 2
1 2 3 4 5
5 4 2 1 3
2 3 1 4 5
4 1 5 2 3
3 5 4 1 2
Output
29
Solution
Compute every \(K\times K\) sub-grid sum using two-dimensional prefix sums.
Two non-intersecting rectangles must be separated either horizontally or vertically. For every possible top-left row, store the best sub-grid starting on that row. Prefix and suffix maxima then give the best pair whose row intervals do not overlap. Repeat the same process for columns.
The complexity is \(O(N^2)\) time and memory.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<vector<long long>> prefix(n + 1, vector<long long>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
long long x;
cin >> x;
prefix[i][j] = x + prefix[i - 1][j] + prefix[i][j - 1]
- prefix[i - 1][j - 1];
}
}
int m = n - k + 1;
const long long NEG = -(1LL << 62);
vector<long long> rowBest(m, NEG), colBest(m, NEG);
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
int bottom = i + k;
int right = j + k;
long long sum = prefix[bottom][right] - prefix[i][right]
- prefix[bottom][j] + prefix[i][j];
rowBest[i] = max(rowBest[i], sum);
colBest[j] = max(colBest[j], sum);
}
}
auto bestSeparated = [&](const vector<long long>& best) {
vector<long long> pref(m), suff(m);
pref[0] = best[0];
for (int i = 1; i < m; i++) {
pref[i] = max(pref[i - 1], best[i]);
}
suff[m - 1] = best[m - 1];
for (int i = m - 2; i >= 0; i--) {
suff[i] = max(suff[i + 1], best[i]);
}
long long answer = NEG;
for (int i = 0; i + k < m; i++) {
answer = max(answer, pref[i] + suff[i + k]);
}
return answer;
};
cout << max(bestSeparated(rowBest), bestSeparated(colBest)) << '\n';
}