Submission #1127619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127619		ttamx	Candies (JOI18_candies)	C++20	100 / 100	524 ms	161916 KiB

candies

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=2e5+5;
const int K=1<<19;

int n;
int a[N];
vector<ll> dp[K][2][2];
vector<ll> ans;
int idx;

void update(vector<ll> &a,const vector<ll> &b){
    for(int i=0;i<b.size();i++){
        if(a.size()==i){
            a.emplace_back(b[i]);
        }else{
            a[i]=max(a[i],b[i]);
        }
    }
}

vector<ll> merge(const vector<ll> &a,const vector<ll> &b){
    if(a.empty()||b.empty())return {};
    vector<ll> c{a[0]+b[0]};
    for(int i=1,j=1;i<a.size()||j<b.size();){
        if(j==b.size()||(i<a.size()&&a[i]-a[i-1]>b[j]-b[j-1])){
            c.emplace_back(a[i]-a[i-1]);
            i++;
        }else{
            c.emplace_back(b[j]-b[j-1]);
            j++;
        }
    }
    for(int i=1;i<c.size();i++){
        c[i]+=c[i-1];
    }
    return c;
}

int dnc(int l,int r){
    int cur=++idx;
    if(l==r){
        dp[cur][0][0]={0LL,a[l]};
        dp[cur][1][1]={0LL};
    }else{
        int m=(l+r)/2;
        int li=dnc(l,m),ri=dnc(m+1,r);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){   
                for(int k=0;k<2;k++){
                    update(dp[cur][i][k],merge(dp[li][i][j],dp[ri][1-j][k]));
                }
            }
        }
    }
    for(int i=1;i>=0;i--){
        for(int j=1;j>=0;j--){
            if(i==0)update(dp[cur][i][j],dp[cur][i+1][j]);
            if(j==0)update(dp[cur][i][j],dp[cur][i][j+1]);
        }
    }
    return cur;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    dnc(1,n);
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            update(ans,dp[1][i][j]);
        }
    }
    for(int i=1;i<=(n+1)/2;i++){
        cout << ans[i] << "\n";
    }
}

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