Submission #1173855

#TimeUsernameProblemLanguageResultExecution timeMemory
1173855zNatsumiHoliday (IOI14_holiday)C++20
24 / 100
5092 ms5704 KiB
#pragma GCC optimize("O3,Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC target("avx2,tune=native,popcnt,lzcnt,fma") #include <bits/stdc++.h> using namespace std; using ii = array<int, 2>; const int N = 1e5 + 5; int n, st, d, a[N]; long long solve(){ long long res = 0, sum = 0; multiset<int> ms; stack<ii> undo; for(int l = st; l >= 0; l--){ if(l < st){ sum += a[l]; ms.insert(a[l]); } for(int r = st; r < n; r++){ int tmp = min(st + r - 2 * l, 2 * r - st - l); if(d <= tmp) break; sum += a[r]; ms.insert(a[r]); undo.push({-1, a[r]}); while(ms.size() > d - tmp){ sum -= *ms.begin(); undo.push({+1, *ms.begin()}); ms.erase(ms.begin()); } res = max(res, sum); } while(undo.size()){ auto [d, x] = undo.top(); undo.pop(); sum += d * x; if(d > 0) ms.insert(x); else ms.erase(ms.find(x)); } } return res; } long long findMaxAttraction(int _n, int start, int days, int attraction[]){ n = _n; st = start; d = days; for(int i = 0; i < n; i++) a[i] = attraction[i]; if(st <= (n - 1)/2){ st = n - 1 - st; for(int i = 0; i <= (n - 1)/2; i++) swap(a[i], a[n - 1 - i]); } return solve(); } //#define zNatsumi #ifdef zNatsumi int main(){ cin.tie(0)->sync_with_stdio(0); #define task "test" if(fopen(task ".inp", "r")){ freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } int n, start, days, attraction[N]; cin >> n >> start >> days; for(int i = 0; i < n; i++) cin >> attraction[i]; cout << findMaxAttraction(n, start, days, attraction); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...