#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back template<typename T1,typename T2>void chmn(T1 &x,const T2 &y){x=x<y?x:y;} template<typename T1,typename T2>void chmx(T1 &x,const T2 &y){x=x>y?x:y;} const int N=2e5+50; const ll INF=1e18; int n,a[N]; vector<ll>dp[4][4*N]; vector<ll>Minkowski(vector<ll>a,vector<ll>b){ int n=a.size(),m=b.size(); vector<ll>c={a[0]+b[0]}; for(int i=1,j=1;i<n||j<m;){ if(i>=n||(j<m&&a[i]-a[i-1]<=b[j]-b[j-1]))c.pb(c.back()+b[j]-b[j-1]),j++; else c.pb(c.back()+a[i]-a[i-1]),i++; } return c; } int lc[2*N],rc[2*N],nc,root; void Solve(int &c,int ss,int se){ c=++nc; if(ss==se){ dp[0][c]={0,-INF}; dp[1][c]={-INF,-INF}; dp[2][c]={-INF,-INF}; dp[3][c]={-INF,a[ss]}; return; } int mid=ss+se>>1; Solve(lc[c],ss,mid); Solve(rc[c],mid+1,se); for(int i=0;i<=3;i++)dp[i][c].resize(se-ss+2,-INF); for(int a=0;a<4;a++)for(int b=0;b<4;b++)if(!(a>>1&1)||!(b&1)){ vector<ll>temp=Minkowski(dp[a][lc[c]],dp[b][rc[c]]); for(int i=0;i<temp.size();i++)chmx(dp[(a&1)^((b>>1&1)<<1)][c][i],temp[i]); } } int main(){ scanf("%i",&n); for(int i=1;i<=n;i++)scanf("%i",&a[i]); Solve(root,1,n); for(int i=1;i<=(n+1>>1);i++)printf("%lld\n",max({dp[0][root][i],dp[1][root][i],dp[2][root][i],dp[3][root][i]})); return 0; }

candies.cpp: In function 'int main()':
candies.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
candies.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~