# 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;
}
```