Submission #1351712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351712		viettrung	Candies (JOI18_candies)	C++20	0 / 100	1 ms	344 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fi first
#define se second
#define mll map<ll, ll>
#define sll set<ll>
const ll du = 1e9 + 7;
const ll ars = 2e5 + 5;

int n;
ll a[ars];
int L[ars], R[ars];
bool used[ars];

priority_queue<pll> pq;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "tenshi"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    f(i,1,n) cin >> a[i];

    f(i,1,n){
        L[i] = i-1;
        R[i] = i+1;
        pq.push({a[i], i});
    }

    int lim = (n + 1) / 2;
    vector<ll> ans;
    ll sum = 0;

    while((int)ans.size() < lim){
        auto top = pq.top(); pq.pop();
        ll val = top.fi;
        int i = top.se;

        if(used[i]) continue;

        sum += val;
        ans.pb(sum);

        int l = L[i];
        int r = R[i];

        if(l >= 1) used[l] = true;
        if(r <= n) used[r] = true;

        int nl = (l >= 1 ? L[l] : 0);
        int nr = (r <= n ? R[r] : n+1);

        if(l >= 1 && r <= n){
            a[i] = a[l] + a[r] - a[i];
            pq.push({a[i], i});
        }

        L[i] = nl;
        R[i] = nr;

        if(nl >= 1) R[nl] = i;
        if(nr <= n) L[nr] = i;
    }

    f(i,0,lim-1) cout << ans[i] << '\n';
}
// 1 (2) 3 (4) 5 (6) 7 8 9
// 1 4 6 8 > 1 3 5 7
// 1 5 7 9 > 1 3 5 7
// 8
// 1 3 5 7

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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