제출 #1128320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128320		SuperVOI	Candies (JOI18_candies)	C++17	100 / 100	97 ms	10076 KiB

candies

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MASK(i) (1LL << (i))
#define GETBIT(i, msk) ((msk >> (i)) & 1)
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())

using namespace std;

const int maxn = 2e5;
const int lim  = 1e6;
const ll  inf  = 1e18;

ll max(ll a,ll b) {return (a > b ? a : b);}
ll min(ll a,ll b) {return (a < b ? a : b);}
ll gcd(ll a,ll b) {return __gcd(a, b);}
ll lcm(ll a,ll b) {return a / gcd(a, b) * b;}
int popcnt(ull n) {return __builtin_popcountll(n);}

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

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

int n;
ll diff[maxn + 5], lef[maxn + 5], rig[maxn + 5];
bool del[maxn + 5];

void solve() {
    for(int i = 1; i <= n; ++i) {
        lef[i] = i - 1;
        rig[i] = i + 1;
    }

    priority_queue<pair<ll, int>> pq;
    for(int i = 1; i <= n; ++i) pq.push(make_pair(diff[i], i));

    ll sum = 0;
    for(int t = 0; t < ((n + 1) >> 1); ++t) {
        while(del[pq.top().se]) pq.pop();

        int i = pq.top().se;
//        cout<<t<<' '<<i<<'\n';
        sum += pq.top().fi; pq.pop();
        cout<<sum<<'\n';

        ll ndiff = -diff[i] + (lef[i] > 0 ? diff[lef[i]] : -inf) +
                (rig[i] <= n ? diff[rig[i]] : -inf);
        diff[i] = ndiff;
        pq.push(make_pair(diff[i], i));

        if(lef[i] > 0) {
            del[lef[i]] = 1;
            lef[i] = lef[lef[i]];
            rig[lef[i]] = i;
        }

        if(rig[i] <= n) {
            del[rig[i]] = 1;
            rig[i] = rig[rig[i]];
            lef[rig[i]] = i;
        }
    }

    return;
}

void input() {
    cin>>n;
    for(int i = 1; i <= n; ++i) cin>>diff[i];
    return;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    freopen("ADN.inp", "r", stdin);
//    freopen("ADN.out", "w", stdout);

    input();
    solve();

    return 0;
}

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