Submission #1322365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322365		StefanSebez	Candies (JOI18_candies)	C++20	100 / 100	688 ms	198020 KiB

candies

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

Compilation message (stderr)

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]);
      |                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92