Maximum Sum with Two Inward Tokens
Autumn Tournament (2019)
Submission name: maxsum.cpp
Problem summary
Two tokens start at positions 1 and N of an integer sequence. The left token moves strictly right and the right token strictly left, using supplied jump lengths. They may stop at any time, but must never meet or cross. Maximize the sum of the values visited by both tokens, including the two starting values.
Input
N K; N sequence values; then K allowed jump lengths.
Output
One integer: the maximum obtainable total.
Constraints
1 < N < 100000; 1 < K < 1000; sequence values are in [−1000,1000]; listed lengths are in [0,N−1].
Worked example
Original statement sample.
Input
9 2 3 2 6 6 0 2 4 5 5 3 2
Output
24
Solution analysis
- Let left[i] be the best sum for the left token when it stops at i. Set left[1]=a[1], and leave initially unreachable positions at a very negative sentinel. For each positive allowed jump d with i−d≥1, try left[i−d]+a[i]. Increasing indices give a valid DP order.
- Compute right[j] symmetrically from N toward 1. For any final i<j, every position visited by the left token is at most i, while every position visited by the right token is at least j. Thus the two independently optimal paths can coexist without meeting or crossing.
- Scan the possible right stopping positions j. Maintain the maximum left[i] over i<j, and combine it with right[j]. This avoids comparing all N² pairs. In the sample, the left token follows 1→3 and collects 3+6=9; the right follows 9→7→4 and collects 5+4+6=15. Their final indices 3<4 remain separated and their total is 24.
Why it works
By induction on i, each left state considers exactly all allowed final jumps of every path from 1 to i; the right states satisfy the analogous invariant. For i<j their paths occupy disjoint index ranges, so their sum is achievable. Conversely every legal pair of paths ends at some i<j and is bounded by those two DP states. Maximizing all such pairs is therefore exact.
Watch out. Keep unreachable states separate from valid negative totals. Stopping immediately is allowed, so a[1]+a[N] is always a candidate. A listed zero length is ignored because the movement rules require a strictly changed index. Do not treat a move of length zero as repeatedly collecting the same cell.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int k;
cin>>n>>k;
vector<int>values(n+1);
for(int i=1;i<=n;i++){
cin>>values[i];
}
vector<int>jumps;
for(int i=0;i<k;i++){
int length;
cin>>length;
if(length>0){
jumps.push_back(length);
}
}
sort(jumps.begin(),jumps.end());
jumps.erase(unique(jumps.begin(),jumps.end()),jumps.end());
const long long unreachable=numeric_limits<long long>::lowest()/4;
vector<long long>left(n+1,unreachable);
vector<long long>right(n+1,unreachable);
left[1]=values[1];
for(int i=2;i<=n;i++){
for(int length:jumps){
if(length>=i){
break;
}
if(left[i-length]!=unreachable){
left[i]=max(left[i],left[i-length]+values[i]);
}
}
}
right[n]=values[n];
for(int i=n-1;i>=1;i--){
for(int length:jumps){
if(i+length>n){
break;
}
if(right[i+length]!=unreachable){
right[i]=max(right[i],right[i+length]+values[i]);
}
}
}
long long answer=unreachable;
long long bestLeft=left[1];
for(int j=2;j<=n;j++){
// Strict separation makes the two independent paths compatible.
if(right[j]!=unreachable){
answer=max(answer,bestLeft+right[j]);
}
bestLeft=max(bestLeft,left[j]);
}
cout<<answer<<'\n';
}