| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 880798 | amogususus | 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.
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=1e5+69;
const int mod=1e9+7;
const int base=311;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rd(ll l,ll r){return rng()%(r-l+1)+l;}
ll n,s,d,a[maxN];
ll f(ll x){
// di tu s -> x xong tu x -> n
ll remain=d-2*(s-x);
if(remain<0)return 0;
priority_queue<ll,vector<ll>,greater<ll>> pq;
ll r=0,sum=0;
for(int i=s-1;i>=x;i--)pq.push(a[i]),sum+=a[i];
for(int i=s;i<=n;i++){
if(remain<=0)return r;
while(pq.size()>remain)sum-=pq.top(),pq.pop();
if(pq.size()<remain||a[i]>pq.top()){
if(pq.size()==remain)sum-=pq.top(),pq.pop();
sum+=a[i];pq.push(a[i]);
}
r=max(r,sum);
remain--;
}
return r;
}
ll findMaxAttraction(int n,int s,int d,int a[])
ll r=0;
for(int _=0;_<=50;_++){
ll x=rd(max(1ll,s-d/2),s);
r=max(r,f(x));
}
for(int i=1;i<=min(20ll,s);i++)r=max(r,f(i));
for(int i=max(1ll,s-20);i<=s;i++)r=max(r,f(i));
reverse(a+1,a+n+1);
s=n+1-s;
for(int i=1;i<=min(20ll,s);i++)r=max(r,f(i));
for(int i=max(1ll,s-20);i<=s;i++)r=max(r,f(i));
for(int _=0;_<=50;_++){
ll x=rd(max(1ll,s-d/2),s);
r=max(r,f(x));
}
return r;
}