Submission #990346

#	Time	Username	Problem	Language	Result	Execution time	Memory
990346		Celebi_276	Candies (JOI18_candies)	C++17	100 / 100	67 ms	9156 KiB

candies

#include <bits/stdc++.h>
using namespace std;

#define      FILE   "TEST"
#define    all(v)   v.begin(), v.end()
#define   rall(v)   v.rbegin(), v.rend()
#define        fi   first
#define        se   second

const int MaxN = 2E5 + 25;
int Prev[MaxN], Next[MaxN];
int n, id;

long long res, cur, a[MaxN];
bool used[MaxN];

void Erase (int id) {
    used[id] = 1;
    if (Prev[id] > 0)  Next[Prev[id]] = Next[id];
    if (Next[id] <= n) Prev[Next[id]] = Prev[id];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    if (fopen(FILE".INP", "r")) {
        freopen(FILE".INP", "r", stdin);
        freopen(FILE".OUT", "w", stdout);
    }
    
    priority_queue <pair <long long, int>> Q;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        Prev[i] = i - 1;
        Next[i] = i + 1;
        Q.emplace(a[i], i);
    }

    for (int i = 1; i <= (n + 1) / 2; i++) {
        while (Q.size() && used[Q.top().second]) Q.pop();

        tie(cur, id) = Q.top();
        Q.pop();

        res += cur;

        if (Prev[id] > 0 && Next[id] <= n) Q.emplace(a[id] = a[Prev[id]] + a[Next[id]] - cur, id);
        else Erase(id);

        if (Prev[id] > 0)  Erase(Prev[id]);
        if (Next[id] <= n) Erase(Next[id]);

        cout << res << "\n";
    }
    
    return 0;
}

Compilation message (stderr)

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

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