Submission #45552

#	Time	Username	Problem	Language	Result	Execution time	Memory
45552		Extazy	Candies (JOI18_candies)	C++17	0 / 100	3 ms	632 KiB

candies

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 200007;

int n,a[N];
bool in[N];
int cnt;
long long sum;
long long ans[N];

void go() {
    vector < pair < int, int > > v;
    vector < long long > g;
    int i;

    ans[cnt]=max(ans[cnt],sum);

    for(i=1;i<=n;i++) if(!in[i]) {
        v.push_back(make_pair(a[i],i));
    }

    sort(v.begin(),v.end());

    for(i=0;i<(int)(v.size());i++) {
        int idx=v[i].second;

        in[idx]=true;
        sum+=a[idx];
        ++cnt;

        if(in[idx-1]) {
            sum-=a[idx-1];
            --cnt;
            in[idx-1]=false;
        }

        if(in[idx+1]) {
            sum-=a[idx+1];
            --cnt;
            in[idx+1]=false;
        }
        
        ans[cnt]=max(ans[cnt],sum);
    }

    for(i=1;i<=n;i++) if(in[i]) {
        g.push_back(a[i]);
    }

    sort(g.rbegin(),g.rend());

    for(i=0;i<(int)(g.size());i++) {
        if(i>0) g[i]+=g[i-1];
        ans[i+1]=max(ans[i+1],g[i]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d", &a[i]);
    }

    assert(n&1);

    for(i=1;i<=n;i+=2) {
        in[i]=true;
        sum+=a[i];
        ++cnt;

    }

    go();

    if(!(n&1)) {
        for(i=1;i<=n;i++) {
            in[i]=false;
        }
        cnt=0;
        sum=0;

        for(i=2;i<=n;i+=2) {
            in[i]=true;
            sum+=a[i];
            ++cnt;
        }
        go();
    }

    for(i=1;i<=(n+1)/2;i++) {
        printf("%lld\n", ans[i]);
    }
    
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
candies.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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