Submission #48559

#	Time	Username	Problem	Language	Result	Execution time	Memory
48559		ngkan146	Candies (JOI18_candies)	C++11	100 / 100	562 ms	19504 KiB

candies

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, a[200005];
typedef pair<int,int> ii;
typedef pair<ll,ii> Iii;
typedef pair<int,Iii> iIii;
priority_queue <Iii> q;
set <Iii> pq;
Iii bounded[200005];

int main(){
    iostream::sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pq.insert(Iii(a[i], ii(i, i)));
        bounded[i] = Iii(a[i], ii(i, i));
    }
    ll summ = 0;
    int boundL = 1;
    int boundR = n;

    for(int _=1;_<=(n+1)/2;_++){
        Iii best;
        while(1){
            best = *pq.rbegin();
            pq.erase(best);
            if (best.second.first < boundL || boundR < best.second.second) continue;
            break;
        }

        summ += best.first;
        Iii tmp = Iii(-best.first, ii(best.second.first-1,best.second.second+1));
        //cout << best.second.first << ' ' << best.second.second << endl;
        //cout << boundL << ' ' << boundR << endl;
        if (tmp.second.first > 0){
            pq.erase(bounded[tmp.second.first]);
            tmp.first += bounded[tmp.second.first].first;
            tmp.second.first = bounded[tmp.second.first].second.first;
        }
        if (tmp.second.second <=n){
            pq.erase(bounded[tmp.second.second]);
            tmp.first += bounded[tmp.second.second].first;
            tmp.second.second = bounded[tmp.second.second].second.second;
        }

        if (tmp.second.first > 0)  bounded[tmp.second.first] = tmp;
        if (tmp.second.second <= n)bounded[tmp.second.second] = tmp;

        cout << summ << '\n';
        if (best.second.first == boundL){
            boundL = best.second.second+2;
            continue;
        }
        if (best.second.second == boundR){
            boundR = best.second.first-2;
            continue;
        }
        pq.insert(tmp);

    }
}

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