# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
517017 | 2022-01-22T11:21:18 Z | amukkalir | Holiday (IOI14_holiday) | C++17 | 1475 ms | 2736 KB |
#include <bits/stdc++.h> #include "holiday.h" using namespace std; typedef long long ll; const int nax = 20; int n; int s, d; int cost (int l, int r) { return (r-l) + min(abs(s-l), abs(r-s)); } bool ok (int mask) { int l=n, r=0; for(int i=0; (1<<i)<=mask; i++) { if(mask & (1<<i)) { l = min(l, i); r = max(r, i); } } int travel = (r-l) + min(abs(s-l), abs(r-s)); return travel + __builtin_popcount(mask) <= d; } long long int findMaxAttraction(int N, int S, int D, int attraction[]) { n = N; s = S; d = D; ll ans = 0; priority_queue<ll, vector<ll>, greater<ll>> pq; ll sum = 0; for(int i=s;i<n;i++){ int rem = d - cost(0,i); if(rem <= 0) break; sum += attraction[i]; pq.push(attraction[i]); while(pq.size() > rem) { sum -= pq.top(); pq.pop(); } priority_queue<ll, vector<ll>, greater<ll>> q; q = pq; ll z = sum; for(int j=s-1; j>=0; j--) { rem = d - cost(j, i); if(rem <= 0) break; z += attraction[j]; q.push(attraction[j]); while(q.size() > rem) { z -= q.top(); q.pop(); } ans = max(ans, z); } ans = max(ans, sum); } return ans; } /* */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 588 KB | Output is correct |
2 | Correct | 0 ms | 588 KB | Output is correct |
3 | Correct | 1 ms | 588 KB | Output is correct |
4 | Correct | 1 ms | 588 KB | Output is correct |
5 | Incorrect | 1 ms | 588 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1265 ms | 2684 KB | Output is correct |
2 | Correct | 1475 ms | 2652 KB | Output is correct |
3 | Correct | 1265 ms | 2736 KB | Output is correct |
4 | Correct | 1320 ms | 2660 KB | Output is correct |
5 | Correct | 998 ms | 1844 KB | Output is correct |
6 | Correct | 115 ms | 1196 KB | Output is correct |
7 | Correct | 293 ms | 1412 KB | Output is correct |
8 | Correct | 363 ms | 1480 KB | Output is correct |
9 | Correct | 46 ms | 1164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 716 KB | Output is correct |
2 | Correct | 1 ms | 716 KB | Output is correct |
3 | Correct | 1 ms | 716 KB | Output is correct |
4 | Incorrect | 88 ms | 736 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 1816 KB | Output is correct |
2 | Correct | 1297 ms | 2576 KB | Output is correct |
3 | Incorrect | 5 ms | 588 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |