Submission #1093153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093153		TrinhKhanhDung	Candies (JOI18_candies)	C++14	100 / 100	75 ms	13448 KiB

candies

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)
#define int ll

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

ll calc(vector<int> arr, int k){
    priority_queue<pair<int, int>> pq;
    int n = sz(arr);

    vector<bool> isDel(n, false);
    vector<int> nxt(n), prv(n);

    for(int i = 0; i < n; i++){
        pq.push({arr[i], i});
        nxt[i] = i + 1;
        prv[i] = i - 1;
    }

    int cur = 0;
    for(int i = 1; i <= k; i++){
        while(isDel[pq.top().se]) pq.pop();

        auto t = pq.top();
        pq.pop();

        cur += t.fi;
        cout << cur << '\n';

        arr[t.se] = - arr[t.se] + (nxt[t.se] < n ? arr[nxt[t.se]] : -oo) + (prv[t.se] >= 0 ? arr[prv[t.se]] : -oo);
        pq.push({arr[t.se], t.se});

        if(prv[t.se] >= 0){
            isDel[prv[t.se]] = true;
            prv[t.se] = prv[prv[t.se]];
            if(prv[t.se] >= 0) nxt[prv[t.se]] = t.se;
        }
        if(nxt[t.se] < n){
            isDel[nxt[t.se]] = true;
            nxt[t.se] = nxt[nxt[t.se]];
            if(nxt[t.se] < n) prv[nxt[t.se]] = t.se;
        }
    }

    return cur;
}

void solve(){
    int n; cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        a.push_back(x);
    }

    calc(a, (n + 1) / 2);
//    int n, k; cin >> n >> k;
//    string s; cin >> s;
//
//    vector<int> ord;
//    int ans = INF;
//
//    int d = 0;
//    for(int i = 0; i < sz(s); i++){
//        d++;
//        if(i + 1 == sz(s) || s[i] != s[i + 1]){
//            ord.push_back(d);
//            d = 0;
//        }
//    }
//
//    if(sz(ord) <= k){
//        cout << 0 << '\n';
//        return;
//    }
//
//    k = sz(ord) - k;
//
//    if(k & 1){
//        vector<int> tmp1;
//        for(int i = 2; i + 1 < sz(ord); i++) tmp1.push_back(ord[i]);
//        minimize(ans, ord[0] + calc(tmp1, k / 2));
//
//        vector<int> tmp2;
//        for(int i = 1; i + 2 < sz(ord); i++) tmp2.push_back(ord[i]);
//        minimize(ans, ord.back() + calc(tmp2, k / 2));
//    }
//    else if(k >= 2) {
//        vector<int> tmp1;
//        for(int i = 2; i + 2 < sz(ord); i++) tmp1.push_back(ord[i]);
//        minimize(ans, ord[0] + ord.back() + calc(tmp1, (k - 2) / 2));
//
//        vector<int> tmp2;
//        for(int i = 1; i + 1 < sz(ord); i++) tmp2.push_back(ord[i]);
//        minimize(ans, calc(tmp2, k / 2));
//    }
//
//    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//     freopen("partner.inp","r",stdin);
//     freopen("partner.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--)
        solve();

    return 0;
}

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