Submission #1035862

#TimeUsernameProblemLanguageResultExecution timeMemory
1035862d4xnHoliday (IOI14_holiday)C++17
40 / 100
5006 ms4644 KiB
#include"holiday.h" #include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() const int N = 1e5; int n, s, d, a[N]; int findMaxAttraction(signed N, signed S, signed D, signed attraction[]) { n = N; s = S; d = D; for (int i = 0; i < n; i++) { a[i] = attraction[i]; } int ans = 0; for (int i = 0; i <= s; i++) { priority_queue<int, vector<int>, greater<int>> pq; int sum = 0; int rem = d - (s-i); if (rem <= 0) continue; vector<int> vt(s-i+1); for (int j = i; j <= s; j++) { vt[j-i] = a[j]; } sort(all(vt)); for (int j = s-i; j >= max(0ll, s-i-rem+1); j--) { sum += vt[j]; pq.push(vt[j]); } rem -= min(rem, s-i+1); ans = max(ans, sum); for (int j = s+1; j < n; j++) { rem = d - pq.size() - (j-i) - min(s-i, j-s); while (rem < 0) { if (pq.empty()) break; sum -= pq.top(); pq.pop(); rem++; } if (rem < 0) break; if (rem) { sum += a[j]; pq.push(a[j]); rem--; } else if (pq.top() < a[j]) { sum -= pq.top(); pq.pop(); sum += a[j]; pq.push(a[j]); } ans = max(ans, sum); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...