Protecting Roses
National Olympiad — Regional round
Submission name: roses.cpp
Problem summary
An M by N grid contains the rose count of each bush. Protect one axis-aligned K by K block of whole cells. Minimize the total number of roses outside that block.
Input
M N K, then the M by N counts.
Output
The minimum number of unprotected roses.
Constraints
0 < K < M,N ≤ 1000; each count is between 0 and 1000.
Worked example
An independently prepared example for this explanation.
Input
2 3 1 1 2 3 4 5 6
Output
15
Solution analysis
- Build two-dimensional prefix sums.
- Obtain every K by K sum from four prefix entries and keep the maximum. Subtract it from the total.
Why it works
Every legal block has a bottom-right corner inspected by the algorithm. Maximizing its protected sum is equivalent to minimizing the remaining total.
Complexity: O(MN) time and space.
Watch out. Return the lost roses, not the protected roses.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every legal block has a bottom-right corner inspected by the algorithm. Maximizing its
// protected sum is equivalent to minimizing the remaining total.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m,n,k;
cin>>m>>n>>k;
vector<vector<long long>>p(m+1,vector<long long>(n+1));
long long best=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
p[i][j]=x+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
if(i>=k&&j>=k){
best=max(best,p[i][j]-p[i-k][j]-p[i][j-k]+p[i-k][j-k]);
}
}
}
cout<<p[m][n]-best<<'\n';
}