# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44890 | 2018-04-09T05:55:46 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 main() { int n; 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(ii(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; ans += w; rounds--; cost[u] = cost[pred[u]]+cost[succ[u]]-cost[u]; dong[pred[u]] = dong[succ[u]] = true; succ[pred[pred[u]]] = u; pred[u] = pred[pred[u]]; pred[succ[succ[u]]] = u; succ[u] = succ[succ[u]]; pq.push(ii(cost[u], u)); printf("%lld\n", ans); } }
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 | - |