# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44898 | 2018-04-09T06:59:35 Z | PowerOfNinjaGo | Candies (JOI18_candies) | C++17 | 3 ms | 504 KB |
//Power Of Ninja Go #include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii; #define X first #define Y second #define pb push_back const int maxn = 2e5+5; int pred[maxn], succ[maxn]; ll cost[maxn]; bool dong[maxn]; int n; bool val(int x) { return x>=1 && x<= n; } int main() { scanf("%d", &n); for(int i = 1; i<= n; i++) { pred[i] = i-1; succ[i] = i+1; } for(int i = 1; i<= n; i++) scanf("%d", &cost[i]); priority_queue< pair<ll, int> > pq; for(int i = 1; i<= n; i++) pq.push(make_pair(cost[i], i)); ll ans = 0; int rounds = (n+1)/2; while(!pq.empty() && rounds) { auto k = pq.top(); pq.pop(); ll w = k.X; int u = k.Y; if(dong[u]) continue; rounds--; ans += cost[u]; printf("%lld\n", ans); bool bad = false; cost[u] = cost[pred[u]]+cost[succ[u]]-cost[u]; dong[pred[u]] = dong[succ[u]] = true; if(pred[u]) { pred[u] = pred[pred[u]]; succ[pred[u]] = u; } else bad = true; if(succ[u] != n+1) { succ[u] = succ[succ[u]]; pred[succ[u]] = u; } else bad = true; if(!bad) pq.push(make_pair(cost[u], u)); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |