# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44891 | 2018-04-09T06:00:28 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; ans += w; rounds--; cost[u] = (val(pred[u])?cost[pred[u]]:0)+(val(succ[u])?cost[succ[u]]:0)-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 | - |