Submission #47913

#TimeUsernameProblemLanguageResultExecution timeMemory
47913Just_Solve_The_ProblemCandies (JOI18_candies)C++11
100 / 100
141 ms65096 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair < ll, ll > #define fr first #define sc second #define mk make_pair #define ll long long const ll inf = (ll)1e15 + 7; const int N = (int)2e5 + 7; int n; priority_queue < pii > q; ll a[N]; int prv[N], nxt[N]; main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); q.emplace(mk(a[i], i)); if (i > 1) prv[i] = i - 1; if (i < n) nxt[i] = i + 1; } ll ans = 0; for (int j = 1; j <= (n + 1) / 2; j++) { while (q.top().fr != a[q.top().sc]) q.pop(); int i = q.top().sc; ans += q.top().fr; printf("%lld\n", ans); int l = prv[i]; int r = nxt[i]; nxt[i] = nxt[r]; prv[i] = prv[l]; nxt[prv[l]] = i; prv[nxt[r]] = i; if (l && r) { a[i] = max(a[l] + a[r] - a[i], -inf); } else { a[i] = -inf; } a[l] = a[r] = -inf; q.emplace(mk(a[i], i)); } }

Compilation message (stderr)

candies.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
candies.cpp: In function 'int main()':
candies.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
candies.cpp:22:10: 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...