#include <bits/stdc++.h> #include "shortcut.h" using namespace std; #define ll long long #define pll pair<ll,ll> #define pb push_back #define fs first #define sc second long long find_shortcut(int n, std::vector<int> L, std::vector<int> D, int C) { ll l[n],d[n]; for(int i=0;i<n-1;i++)l[i]=L[i]; l[n-1]=0; for(int i=0;i<n;i++)d[i]=D[i]; ll c=C; ll c1[n],c2[n]; c1[0]=d[0]; for(int i=1;i<n;i++)c1[i]=max(c1[i-1]+l[i-1],d[i]); c2[n-1]=d[n-1]; for(int i=n-2;i>-1;i--)c2[i]=max(c2[i+1]+l[i],d[i]); ll m1[n],m2[n]; m1[0]=d[0]; for(int i=1;i<n;i++)m1[i]=max(m1[i-1],d[i]+l[i-1]+c1[i-1]); m2[n-1]=d[n-1]; for(int i=n-2;i>-1;i--)m2[i]=max(m2[i+1],d[i]+l[i]+c2[i+1]); auto clc=[&](int x,int y){ ll dx=d[x],dy=d[y],ly=l[y]; d[x]=c1[x]; d[y]=c2[y]; l[y]=c; ll s=0; for(int i=x;i<=y;i++)s+=l[i]; s/=2; deque<pll> dq; dq.pb({x,d[x]}); ll mx=max(m1[x],m2[y]); for(ll i=x,j=x,pi=0,pj=0;i<=y;i++){ while(pj+l[j]-pi<=s){ pj+=l[j]; j++; if(j>y)j=x; ll t=pj+d[j]; while(!dq.empty()&&dq.back().sc<t)dq.pop_back(); dq.pb({j,t}); } if(dq.front().fs==i)dq.pop_front(); if(!dq.empty()){ mx=max(mx,dq[0].sc-pi+d[i]); } pi+=l[i]; } d[x]=dx; d[y]=dy; l[y]=ly; return mx; }; ll ans=1e18; for(int x=0;x<n;x++){ int l=x+1,r=n-1; while(l<r){ int m=l+r>>1; if(clc(x,m)<clc(x,m+1))r=m; else l=m+1; } ans=min(ans,clc(x,l)); } return ans; }

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~