oj.uz

답안 #862500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862500 2023-10-18T11:19:21 Z eitanelb Candies (JOI18_candies) C++14
0 / 100
 2 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;
//#include"nuts.h"

#define ll long long
#define x first
#define y second
#define pi pair<ll,ll>

vector<long long> Nuts(int n, vector<int> v){
    priority_queue<pi> pq;
    ll l[n],r[n];
    for(ll i=0;i<n;i++){
        pq.push({v[i],i});
        l[i]=i-1;r[i]=i+1;
    }
    vector<bool> vis(n,0);
    ll res=0;
    vector<ll> ans;
    for(ll i=0; i< (n+1)/2;i++){
        while(vis[pq.top().y]) pq.pop();
        pi p = pq.top(); pq.pop();
        res += p.x;
        ans.push_back(res);
        ll cur = p.y;
        if(r[cur]==n){
            vis[cur]=1;
            if(l[cur]!=-1)vis[l[cur]]=1;
            if(l[l[cur]] > -1) r[l[l[cur]]]=n;
        }
        else if(l[cur]==-1){
            vis[cur]=1;
            if(r[cur]!=n)vis[r[cur]]=1;
            if(r[r[cur]] < n) l[r[r[cur]]]=-1;
        }
        else{
            v[cur] = v[r[cur]]+v[l[cur]] - v[cur];
            vis[r[cur]]=1;
            r[cur] = r[r[cur]];
            if(r[cur] != n) l[r[cur]]=cur;
            vis[l[cur]]=1;
            l[cur] = l[l[cur]];
            if(l[cur] != -1) r[l[cur]]=cur;
            pq.push({v[cur],cur});
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int> nuts(n);
    for(int i=0;i<n;i++) cin>>nuts[i];
    
    vector<long long> ans = Nuts(n, nuts);
    
    for(long long c : ans) cout<<c<<endl;
    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -