제출 #1190759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190759		AlgorithmWarrior	Candies (JOI18_candies)	C++20	0 / 100	1 ms	576 KiB

candies

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=200005;
long long sppar[MAX],spimp[MAX];
int n;
long long v[MAX];
int cst[MAX],cdr[MAX];
long long val[MAX];
class cmp{
public:
    bool operator()(int a,int b)const{
        return val[a]>=val[b];
    }
};
set<int,cmp>s;

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    v[0]=-INF;
    v[n+1]=-INF;
}

void precalc(){
    sppar[0]=v[0];
    sppar[1]=v[0];
    spimp[0]=0;
    spimp[1]=v[1];
    int i;
    for(i=2;i<=n+1;++i)
        if(i&1){
            spimp[i]=spimp[i-1]+v[i];
            sppar[i]=sppar[i-1];
        }
        else{
            spimp[i]=spimp[i-1];
            sppar[i]=sppar[i-1]+v[i];
        }
}

void init(){
    int i;
    for(i=0;i<=n+1;++i){
        cst[i]=i;
        cdr[i]=i;
        val[i]=v[i];
        s.insert(i);
    }
}

long long sp(int l,int r,long long sump[]){
    long long ans=sump[r];
    if(l>0)
        ans-=sump[l-1];
    return ans;
}

void solve(){
    long long ans=0;
    int i;
    for(i=1;i<=(n+1)/2;++i){
        int id=*s.begin();
        ans+=val[id];
        cout<<ans<<'\n';
        s.erase(id);
        int l=cst[id-1];
        int r=cdr[cdr[id]+1];
        s.erase(l);
        s.erase(cst[r]);
        cdr[l]=r;
        cst[r]=l;
        if(l&1)
            val[l]=sp(l,r,spimp)-sp(l,r,sppar);
        else
            val[l]=sp(l,r,sppar)-sp(l,r,spimp);
        s.insert(l);
    }
}

int main()
{
    read();
    precalc();
    init();
    solve();
    return 0;
}

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