HEALTHY MOMOS - APOC2_02 - EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
HARD
PREREQUISITES
Dynamic Programming
PROBLEM
Nitin entered Chef’s-Momos, and he was guided to the counter.He picks momos as he travels
However, while walking, he consumes 1 kilocalories per meter. Whenever he is satisfied, he can leave the restaurant from any place
(he does not have to return to the initial place). On balance, at most how much nutrition can he take in before he leaves?
That is, what is the maximum possible value of the total nutrition taken in minus the total energy consumed?
EXPLANATION
Imagine that his shoes are wet with paint, and he paints the floor where he walks. In the end, he eats
all momos in the painted segment.
Let the initial place be O, and the painted segment in the end be arc AB (If we walk clockwise from
O, we reach A first. We ignore the case where the whole counter is painted, which is not optimal). Note
that A and/or B may coincide with O. The optimal way to walk is to ”walk clockwise until A, then
turn around and walk counterclockwise until B”, or ”walk counterclockwise until B, then turn around
and walk clockwise until A”.
The distance covered in the first way of walking is OA + AB = 2OA + OB, and OA + 2OB in the
second way. When A and B is fixed, it is optimal to perform the first way if OA ≥ OB, and the second
way if OA ≥ OB, but we actually don’t have to care this too much. We just need to find the optimal
solution when we stick to the first way, and the optimal solution when we stick to the second way, and
take the better one. We will deal with the second way from now on (the first way can be dealt similarly).
One more observation is required to find the solution, both A and B must be a position where a momo is
placed or O. This is because the arc could be shortened without losing a momo otherwise. Thus, the partial
test set can be solved with trying every possible choice of A and B. This results in an O(N3) time solution
if implemented naively, and O(N2) if v1, v1+v2, …, v1+v2+…+vN and vN , vN +vN−1, …, vN +vN−1+…+v1
are precomputed.
The full test set can be solved with just a little improvement from here. There is enough time to try
every choice of A or B, and we will go with B here. When B is fixed as xb, A is one of x1, x2, …, xb−1,
and we should select xa corresponding to a that maximizes f(a) := v1 + v2 + … + va − xa. (This
is because, the calories taken in is equal to f(a) plus vN + vN−1 + … + vb − (C − xb), which has a
constant value independent of a when b is fixed). Thus, if we find f(0), f(1), …, f(N) beforehand, and
find g(a) := max(f(0), f(1), …, f(a)) for each a = 0, 1, …, N (starting from g(0)), we can immediately
make the optimal choice of A when B is fixed, thus we have an O(N) time solution.
PROGRAM
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define N 214514
const ll mod=1000000007;
ll x[N],v[N],rote[2][N];
int main(){
ll n,c;
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>x[i]>>v[i];
ll sum=0;
for(int i=1;i<=n;i++){
sum+=v[i]-x[i]+x[i-1];
rote[0][i]=max(rote[0][i-1],sum);
}
sum=0;
x[n+1]=c;
for(int i=n;i>=1;i--){
sum+=v[i]-x[i+1]+x[i];
rote[1][i]=max(rote[1][i+1],sum);
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=max({ans,rote[0][i]+rote[1][i+1]-
x[i],rote[0][i],rote[1][i]+rote[0][i-1]-c+x[i],rote[1][i]});
}
cout<<ans;
return 0;
}