Problem name: Feast

Problem Statement:
Alice has decided to visit a restaurant with a circular food conveyor belt. The belt has
a circumference of C meters, and guests are seated around the outer edge of the
belt, unable to step inside.
On the belt, there are N different dishes at specific positions. The distance from
Alice's starting point to the location of the i-th dish is Xi meters, and the dish provides
Vi kilocalories of energy.
Alice can walk along the belt to grab dishes, consuming the calories each one offers.
However, for every meter she walks, she burns 1 kilocalorie. She can stop and leave
the belt from any point once she is satisfied, without needing to return to her starting
position.
Your task is to help Alice maximize her net energy gain. How much nutrition can Alice
collect after deducting the calories she burns walking?
Brute Force Method:
This code finds the maximum possible value based on position and corresponding
values, employing dynamic programming to store and combine results.
Time Complexity
The time complexity of the brute force method is: O(N^2)
Space Complexity
The space complexity of the brute force method is: O(N)

Implementation:
Two vectors x and v are initialized, where x stores positions and v stores values
corresponding to those positions.
It reads n pairs of values, filling x with positions and v with their respective values.
It appends c to the vector x, marking the end position.
Two dynamic programming arrays (a1 and a2) are used to store intermediate results:
 a1 calculates the maximum possible value starting from the left.
 a2 calculates the maximum possible value starting from the right.
The first loop fills a1 based on the values and positions in x and v.
The second loop fills a2 similarly but in reverse order.
Two nested loops then combine the values of a1 and a2 to find the maximum
possible values for different combinations.
Output: The final maximum value is printed.
Code:
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion

int main(void) {
vll x, v, a1, a2;
ll c;
cin >> n >> c;
x.pb(0);
FOR(i, 0, n) {
cin >> tmp;
 x.pb(tmp);
cin >> tmp;
v.pb(tmp);
}
x.pb(c);
a1.pb(0);
FOR(i, 0, n) {
m = a1[i] + v[i] - (x[i + 1] - x[i]);
ans = max(ans, m);
a1.pb(m);
}

a2.pb(0);
FOR(i, 0, n) {
m = a2[i] + v[n - i - 1] - (x[n - i + 1] - x[n - i]);
ans = max(ans, m);
a2.pb(m);
}

FOR(i, 1, n + 1) {
FOR(j, 1, n - i + 1 ) {
m = a1[i] + a2[j] - x[i];
ans = max(ans, m);
}
}

FOR(i, 1, n + 1) {
FOR(j, 1, n - i + 1) {
m = a1[j] + a2[i] - (c - x[n - i + 1]);
ans = max(ans, m);
}
}

cout << ans << endl;

return 0;
}

Optimized Solution: This code efficiently computes a maximum value based on a

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100005,LG=17;
int n;
ll C;
ll x[N],a[N],asum[N],atot[N];
ll init_val[N];
ll y[N],b[N],bsum[N];
struct ST{
ll s[N][22];
void init()
{
for(int i=1;i<=n;i++)
s[i][0]=init_val[i];
for(int j=1;j<=LG;j++)
for(int i=1;i+(1<<j)<=n;i++)
s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
ll query(int l,int r)
{
if(l>r) return 0ll;
int k=(int)floor(log(r-l+1)/log(2));
return max(max(s[l][k],s[r-(1<<k)+1][k]),0ll);
}
};
ST c1,c2;
int main()
{
scanf("%d%lld",&n,&C);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&x[i],&a[i]);
y[n-i+1]=C-x[i];
b[n-i+1]=a[i];
}
for(int i=1;i<=n;i++) bsum[i]=bsum[i-1]+b[i];
for(int i=1;i<=n;i++)
{
asum[i]=asum[i-1]+a[i];
atot[i]=asum[i]-x[i];
}
for(int i=1;i<=n;i++)
init_val[i]=bsum[i]-y[i];
 c1.init();
for(int i=1;i<=n;i++)
init_val[i]=bsum[i]-y[i]-y[i];
c2.init();
ll ans=0;
for(int i=1;i<=n;i++) ans=max(ans,atot[i]);
for(int i=1;i<=n;i++) ans=max(ans,bsum[i]-y[i]);
ll ans1,ans2;
for(int i=1;i<=n;i++)
{
ans1=c1.query(1,n-i)+asum[i]-x[i]-x[i];
ans2=c2.query(1,n-i)+asum[i]-x[i];
ans=max(ans,max(ans1,ans2));
}
printf("%lld",ans);
return 0;
}

Implementation:
 The program reads input values for n and C.
 It then reads the x-coordinates and values into arrays x and a.
 A mirrored array is created for y and b to handle calculations efficiently.
 The cumulative sums of the b array are stored in bsum, and similar operations are
performed for a and x to calculate asum and atot.
 The initialization value for the Sparse Table is computed using bsum and y.
 Two Sparse Tables, c1 and c2, are initialized with modified initialization values.
 The maximum value ans is updated by considering:
 The maximum of atot and bsum - y[i].
 Results from range queries using the Sparse Table.
Final Calculation:
 The program iterates through the points to find the maximum values using the
results from the Sparse Table queries.
 The final result is printed.