Submission #48412

#TimeUsernameProblemLanguageResultExecution timeMemory
48412choikiwonCandies (JOI18_candies)C++17
100 / 100
146 ms65368 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MN = 200010; int N; ll A[MN]; int pre[MN], nxt[MN]; priority_queue<pair<ll, int> > pq; int main() { scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%lld", &A[i]); } for(int i = 0; i < N; i++) { pre[i] = i - 1; nxt[i] = i + 1; pq.push({ A[i], i }); } ll sum = 0; for(int i = 1; i <= (N + 1) / 2; i++) { pair<ll, int> t = {-1, -1}; while(!pq.empty()) { t = pq.top(); pq.pop(); if(A[t.second] == t.first) break; } sum += t.first; printf("%lld\n", sum); A[t.second] = -A[t.second]; bool ok = true; if(pre[t.second] != -1) { A[t.second] += A[ pre[t.second] ]; A[ pre[t.second] ] = -1e18; pre[t.second] = pre[ pre[t.second] ]; if(pre[t.second] != -1) nxt[ pre[t.second] ] = t.second; } else ok = false; if(nxt[t.second] != N) { A[t.second] += A[ nxt[t.second] ]; A[ nxt[t.second] ] = -1e18; nxt[t.second] = nxt[ nxt[t.second] ]; if(nxt[t.second] != N) pre[ nxt[t.second] ] = t.second; } else ok = false; if(ok) pq.push({ A[t.second], t.second }); else A[t.second] = -1e18; } }

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
candies.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &A[i]);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...