oj.uz

답안 #565487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
565487 2022-05-21T00:58:21 Z lohacho Candies (JOI18_candies) C++14
0 / 100
 3 ms 724 KB 
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    set<vector<int>> st1, st2;
    for(int i = 0; i < n; ++i){
        st1.insert({i, a[i], 1});
        st2.insert({a[i], i, 1});
    }
    int cnt = 0, sum = 0;
    while(cnt < (n + 1) / 2){
        auto p2 = prev(st2.end());
        int nowi = (*p2)[1];
        cnt += (*p2)[2], sum += (*p2)[0];
        if((*p2)[2] > 0){
            cout << sum << '\n';
        }
        int dcnt = -(*p2)[2], dsum = -(*p2)[0];
        auto p1 = st1.lower_bound(vector<int>{nowi, -(int)1e18, -(int)1e18});
        if(p1 != st1.begin()){
            auto p1p = prev(p1);
            dsum += (*p1p)[1];
            dcnt += (*p1p)[2];
            st2.erase(st2.find(vector<int>{(*p1p)[1], (*p1p)[0], (*p1p)[2]}));
            st1.erase(p1p);
        }
        auto p1n = next(p1);
        if(p1n != st1.end()){
            dsum += (*p1n)[1];
            dcnt += (*p1n)[2];
            st2.erase(st2.find(vector<int>{(*p1n)[1], (*p1n)[0], (*p1n)[2]}));
            st1.erase(p1n);
        }
        st2.insert({dsum, nowi, dcnt});
        st1.insert({nowi, dsum, dcnt});
        st2.erase(p2);
        st1.erase(p1);
    }
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 92.0

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