# HEALTHY MOMOS APOC2_05 SOLUTION

Page Contents

## HEALTHY MOMOS SOLUTION

“Chef’s-Momos”, an Indian restaurant, is a plain restaurant with only one round counter. The outer circumference of the counter is C meters. Customers cannot go inside the counter. Nitin entered Chef’s-Momos, and he was guided to the counter. Now, there are N pieces of momos (vinegared rice with seafood and so on) on the counter. The distance measured clockwise from the point where Nitin is standing to the point where the i-th momo is placed, is xi meters. Also, the i-th momo has a nutritive value of vi kilocalories.

Nitin can freely walk around the circumference of the counter. When he reach a point where a momo is placed, he can eat that momo and take in its nutrition (naturally, the momo disappears). 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? Assume that there are no other customers, and no new momo will be added to the counter. Also, since Nitin has plenty of nutrition in his body, assume that no matter how much he walks and consumes energy, he never dies from hunger.

Constraints
1≤N≤105
2≤C≤1014
1≤x1< x2 < … < xN < C
1≤vi≤109
All values in input are integers.

Input Format
Input is given from Standard Input in the following format:
N C
x1 v1
x2 v2
:
xN vN

Output
If Nitin can take in at most c kilocalories on balance before he leaves the restaurant, print c.

Example Text Case:
Input:
3 20
2 80
9 120
16 1

Output:
191

Explanation
NOTE: There are three momos on the counter with a circumference of 20 meters. If he
walks two meters clockwise from the initial place, he can eat a momo of 80 kilocalories.
If he walks seven more meters clockwise, he can eat a momo of 120kilocalories.
If he leaves now, the total nutrition taken in is 200 kilocalories,
and the total energy consumed is 9 kilocalories, thus he can take in 191 kilocalories on
balance, which is the largest possible value.

## Solution:

Program Python:

```import sys
n, c = map(int, input().strip().split())
posit=[]
for _ in range(n):
x, v= map(int, input().strip().split())
posit.append((v, x, c-x))
clock_sum=[posit[0][0]]
counter_sum=[posit[n-1][0]]
massimo=max(0,posit[0][0]-posit[0][1])
massimo=max(massimo,posit[n-1][0]-posit[n-1][2])
for i in range(1,n):
clock_sum.append(clock_sum[-1]+posit[i][0])
massimo=max(massimo, clock_sum[i]-posit[i][1])
counter_sum.append(counter_sum[-1]+posit[n-1-i][0])
massimo=max(massimo, counter_sum[i]-posit[n-1-i][2])
for i in range(n-1):
for j in range(n-1,i,-1):
appo=min(posit[i][1], posit[j][2])
massimo=max(massimo, clock_sum[i]+ counter_sum[n-j-1]-appo-posit[i][1]-posit[j][2])
print(massimo)```

Program C++:

```#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, c;
cin >> n >> c;
vector<int> pts(n), cost(n);
vector<pair<int, int>> vec(n);
int i;
for(i=0;i<n;i++)
cin >> vec[i].first >> vec[i].second;
sort(vec.begin(), vec.end());
for(i=0;i<n;i++)
pts[i] = vec[i].first, cost[i] = vec[i].second;

int ans = 0, sum = 0;
for(i=0;i<n;i++)
{
sum+=cost[i];
ans = max(ans, sum - pts[i]);
}

sum = 0;
for(i=n-1;i>=0;i--)
{
sum+=cost[i];

ans = max(ans, sum - (c - pts[i]));
}

vector<int> forw(n), back(n);
forw[0] = cost[0] - 2*pts[0];
for(i=1;i<n;i++)
forw[i] = forw[i-1] + cost[i] + 2*pts[i-1] - 2*pts[i];
back[0] = cost[n-1] - (c - pts[n-1]);
for(i=1;i<n;i++)
back[i] = back[i-1] + cost[n-i-1] + (c - pts[n-i]) - (c - pts[n-i-1]);

for(i=1;i<n;i++)
forw[i] = max(forw[i], forw[i-1]);
int j;
for(j=0;j<n-1;j++)
ans = max(ans, back[j] + forw[n-2-j]);

forw[0] = cost[0] - pts[0];
for(i=1;i<n;i++)
forw[i] = forw[i-1] + cost[i] + pts[i-1] - pts[i];

back[0] = cost[n-1] - 2*(c - pts[n-1]);
for(i=1;i<n;i++)
back[i] = back[i-1] + cost[n-i-1] + 2*(c - pts[n-i]) - 2*(c - pts[n-i-1]);

for(i=1;i<n;i++)
forw[i] = max(forw[i], forw[i-1]);

for(j=0;j<n-1;j++)
ans = max(ans, back[j] + forw[n-2-j]);
cout << ans;

}```

Program Java:

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long c = sc.nextLong();
long x[] = new long[n];
long v[] = new long[n];
for(int i = 0 ; i < n ; i++)
{
x[i] = sc.nextLong();
v[i] = sc.nextLong();
}

long max[] = new long[n];
long curr = 0;
for(int i = n-1 ; i >= 0 ; i--)
{
if(i==n-1)
curr -= (c-x[n-1]);

else
curr -= x[i+1]-x[i];

curr += v[i];

if(i==n-1)
max[i] = curr;

else
max[i] = Math.max(max[i+1],curr);
}

curr = 0;
long mx = 0;
mx = Math.max(mx,max[0]);
long max2[] = new long[n];
for(int i = 0 ; i < n ; i++)
{
if(i==0)
curr -= x[i];

else
curr -= x[i]-x[i-1];

curr += v[i];

if(i==0)
max2[i] = curr;

else
max2[i] = Math.max(curr,max2[i-1]);
mx = Math.max(mx,curr);
if(i < n-1)
mx = Math.max(mx,curr-x[i]+max[i+1]);

}
curr = 0;
for(int i = n-1 ; i >= 0 ;i--)
{
if(i==n-1)
curr -= (c-x[i]);

else
curr -= x[i+1]-x[i];

curr += v[i];

if(i != 0)
mx = Math.max(mx,curr - (c-x[i]) + max2[i-1]);
}
System.out.println(mx);
}
}```