Submission #669553

#	Time	Username	Problem	Language	Result	Execution time	Memory
669553		LCJLY	Candies (JOI18_candies)	C++14	0 / 100	2 ms	468 KiB

candies

#include <bits/stdc++.h>
using namespace std;
 
#define ull unsigned long long
#define unint unsigned int
#define sint short int
#define usint unsigned short int
#define ll long long
#define ld long double
#define vt vector
#define pb push_back
#define mp make_pair
#define PI 3.14159265358979323
#define F first
#define S second 
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)a.size())
#define clr(x,a) memset(x, a, sizeof(x))
#define len(a) ((int)a.length())
#define E 2.7182818284590452353602874713527
#define FOR(i, x) for(int i=0; i<x; ++i)
#define For(i, x) for(auto& i: x)
#define RFOR(i, x) for(int i=x-1; i>=0; --i) 
#define FORS(x, s, e, n) for(int x=s; x<=e; x+=n) 
#define int long long

typedef pair<int, int> pii;
 
void solve(){
    
}
 
int32_t main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    int a;
    cin >> a;
    set<int>s;
    int temp;
    priority_queue<pii>pq;
    set<ll>::iterator low;
    int arr[a];
    for(int x=0;x<a;x++){
        cin >> temp;
        arr[x]=temp;
        s.insert(x);
        pq.push(make_pair(temp,x));
    }

    int counter=0;
    for(int x=0;x<(a+1)/2LL;x++){
        pii cur=pq.top();
        pq.pop();
        while(s.find(cur.second)==s.end()&&!pq.empty()){
            cur=pq.top();
            pq.pop();
        }
        counter+=cur.first;
        cout << counter << "\n";
        // cout << "amos" << " " << cur.first << "\n";
        int lefttarget=cur.second;
        bool hayden=true;
        low=s.lower_bound(lefttarget);
        if(low==s.begin()){
            hayden=false;
        }
        low--;
        int leftind=*low;
        int righttarget=cur.second+1;   
        int rightind=*s.lower_bound(righttarget);
        // cout << leftind << " " << rightind << "-<\n";
        if(s.find(leftind)!=s.end()){
            s.erase(leftind);   
        }
        if(s.find(rightind)!=s.end()){
            s.erase(rightind);
        }
        // s.erase(s.find(leftind));
        // s.erase(s.find(rightind));
        int neighbour=0;
        if(leftind>=0&&leftind<a&&hayden){
            neighbour+=arr[leftind];
        }
        if(rightind<a){
            neighbour+=arr[rightind];
        }
        // cout << " " << neighbour << " " << cur.first << " " << neighbour-cur.first << "$\n";
        arr[cur.second]=neighbour-cur.first;
        pq.push(make_pair(neighbour-cur.first,cur.second));
        // for(auto it:s){
        //     cout << it << " ";
        // }
        // cout << "\n";
    }

    return 0;
}   

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