| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 237039 | crossing0ver | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include"holiday.h"
#define ll long long
#define fi first
#define se second
using namespace std;
int n,x,d,val[100005];
ll solveR() {
set <pair<int,int> > s;
ll eaten = 0,ans = val[x];
int left = 0;
eaten = val[x];
s.insert({val[x],x});
for (int i = x + 1; i < n; i++) {
int stamina = i + s.size();
if (i >= d) {left = i + 1; break;}
while (stamina >= d) {
eaten -= (*s.begin()).fi;
s.erase(s.begin());
stamina--;
}
if (stamina < d) {
eaten += val[i];
s.insert({val[i],i});
}
ans = max(ans,eaten);
}
return ans;
}
ll solve() {
set <pair<int,int> > s;
ll eaten = 0,ans = val[x];
int left = 0;
for (int i = x; i >= 0; i--) {
s.insert({val[i],i});
eaten += val[i];
}
int l = 0;
for (int i = x + 1; i < n && i < x + d; i++) {
int stamina = i - x + i - l + s.size();
while (stamina >= d) {
if (i - x + i - l >= d) {
stamina--;
if (s.find({val[l],l}) != s.end()) {
stamina--;
s.erase({val[l],l});
eaten -= val[l];
}
l++;
}
else {
if (s.find({val[l],l}) == s.end()) {
l++;
stamina--;
continue;
}
int in = (*s.begin()).se;
eaten -= (*s.begin()).fi;
if (in == l && l < x) {
l++;
if ( l != x)
stamina-=2;
else stamina--;
}
else stamina--;
s.erase(s.begin());
}
}
s.insert({val[i],i});
eaten += val[i];
ans = max(ans,eaten);
}
return ans;
}
long long int findMaxAttraction(int n1, int start, int d1, int attraction[]) {
n = n1;
x = start;
d = d1;
ll ans = 0;
if (!d) return 0;
if (d == 1) return val[start];
for (int i = 0; i < n; i ++) val[i] = attraction[i];
ans = max(ans,solveR());
ans = max(ans,solve());
for (int i = 0 ;i < n; i++) val[i] = attraction[n-i];
x = n - x;
ans = max(ans,solveR());
ans = max(ans,solve());
return ans;
}
main(){
int n,start,d;
cin >> n >> start >> d;
int att[n];
for (int i = 0; i < n ;i ++) cin >> att[i];
cout << findMaxAttraction(n,start,d,att);
}