Sum of Products
National Olympiad — Regional round (2014 season)
Submission name: sumprod.cpp
Problem summary
Maximize Σ ai*pi, choosing integer pi between b and c, with |pi−p(i−1)|≤d for adjacent positions. Only the maximum value is required.
Input
n b c d, followed by n integers ai.
Output
The maximum sum.
Constraints
0 < n < 100000; −9 ≤ ai ≤ 9; 0 < b < c < 10; 0 < d < 10.
Worked example
Official statement sample.
Input
4 2 4 1 2 -3 5 -1
Output
16
Solution analysis
- Let dp[p] be the best sum for the processed prefix whose last selected value is p. There are at most eight possible values, so every predecessor can be checked directly.
- For the next coefficient a, set next[p]=a*p+max(dp[q]) over b≤q≤c and |p−q|≤d. Initialize every dp[p] to zero before reading any coefficients; this allows any first value. Use a new array so updates within one position cannot affect one another.
- In the sample the choices 4,3,4,3 respect the difference limit and give 8−9+20−3=16. The final answer is the largest state after all four positions.
Why it works
For any optimal prefix ending at p, its preceding value q must lie within distance d, and deleting the final term leaves an optimal prefix for q, or it could be improved. The recurrence examines all and only these legal predecessors. Induction over positions establishes all states and the final maximum.
Watch out. Negative coefficients are allowed; do not initialize unreachable intermediate states to zero or greedily choose endpoints independently.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<limits>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,b,c,d;
cin>>n>>b>>c>>d;
vector<long long>dp(c+1,0);
for(int i=0;i<n;++i){
int a;
cin>>a;
// A state records the last chosen p; only nearby predecessors are legal.
vector<long long>next(c+1,numeric_limits<long long>::lowest()/4);
for(int p=b;p<=c;++p){
for(int q=b;q<=c;++q){
if(abs(p-q)<=d){
next[p]=max(next[p],dp[q]+a*p);
}
}
}
dp.swap(next);
}
cout<<*max_element(dp.begin()+b,dp.end())<<'\n';
}