Escape from Raspberry
Autumn Tournament (2023)
Submission name: raspberry.cpp
Problem summary
From a starting grid cell, collect its value and repeatedly jump southeast to any different cell whose row and column are both no smaller. You may leave the grid immediately. Find the sum, over all starting cells, of the maximum obtainable value.
Input
N M, then an N by M grid of signed values.
Output
The sum of all optimal starting-cell scores.
Constraints
1 ≤ N,M ≤ 500; −1000 ≤ aij ≤ 1000.
Worked example
Original statement sample.
Input
4 3 1 2 3 -2 -3 0 -1 4 -2 3 -1 -1
Output
25
Solution analysis
- Let best[i][j] be the optimal score when starting at (i,j). The first cell is mandatory; after eating it, either leave for an additional0 or choose any cell in its southeast rectangle except itself.
- Process rows and columns in reverse order. Store suffix[i][j], the largest best value in the rectangle from (i,j) to the bottom-right corner, allowing0 for leaving. The future rectangle excluding (i,j) is the union of suffix[i+1][j] and suffix[i][j+1]. Thus best=aij+max(those two values). Update the suffix maximum and add best to the answer.
- In the sample, best[2][1]=−2+4=2 by jumping to(3,2) and leaving. The best-score rows are [7,6,3], [2,1,0], [3,4,−2], [3,−1,−1], whose sum is25. Negative starts remain negative when every possible continuation is worse than leaving.
Why it works
Every allowed next cell belongs to one of the two stored suffix rectangles, and each cell in those rectangles is a legal next cell. Reverse iteration makes their optimal scores available. Choosing their maximum or0 therefore implements the exact recurrence; induction proves all starting scores and their sum.
Watch out. The starting cell must be eaten even when negative. Do not add0 as an alternative to the entire best score. Use long long for the sum across up to250000 starts.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<int>>value(n+2,vector<int>(m+2));
vector<vector<int>>suffix(n+2,vector<int>(m+2,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>value[i][j];
}
}
long long answer=0;
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
int continuation=max(suffix[i+1][j],suffix[i][j+1]);
int best=value[i][j]+continuation;
answer+=best;
// Zero represents the option of leaving the grid.
suffix[i][j]=max(0,max(best,continuation));
}
}
cout<<answer<<'\n';
}