| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1019558 | pcc | 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"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct DS{
priority_queue<ll,vector<ll>,greater<ll>> pq;
ll sum = 0;
DS(){
sum = 0;
}
void init(){
sum = 0;
while(!pq.empty())pq.pop();
}
void add(ll k){
pq.push(k);
sum += k;
}
void shape(int len){
while(!pq.empty()&&(ll)pq.size()>len){
sum -= pq.top();
pq.pop();
}
assert(pq.empty()||pq.size()<=len);
return;
}
};
namespace ZERO{
const ll mxn = 1e5+10;
DS ds;
ll GO(int n,int s,int d,int arr[]){
ds.init();
ll ans = 0;
for(int i = 0;i<=min(d,n-1);i++){
ds.add(arr[i]);
int rest = d-i;
ds.shape(d-i);
ans = max(ans,ds.sum);
}
return ans;
}
}
namespace BRUTE{
const ll mxn = 3030;
int tr1[mxn],tr2[mxn];
ll arr[mxn];
DS ds;
int n,s,d;
ll calc(int e){
ll re = 0;
ds.init();
for(int i = e;i>s;i--)ds.add(arr[i]);
ll tans = 0;
for(int i = s;i>=0;i--){
ds.add(arr[i]);
int rest = d-((e-s)*2+(s-i));
ds.shape(rest);
//cerr<<"L FIRST: "<<i<<' '<<e<<"::"<<rest<<','<<ds.pq.size()<<','<<ds.sum<<endl;
if(tans<ds.sum){
tans = ds.sum;
tr1[e] = i;
}
}
re = max(re,tans);
ds.init();
tans = 0;
for(int i = e;i>s;i--)ds.add(arr[i]);
for(int i = s;i>=0;i--){
ds.add(arr[i]);
int rest = d-((e-s)+(s-i)*2);
ds.shape(rest);
if(tans<ds.sum){
tans = ds.sum;
tr2[e] = i;
}
}
re = max(re,tans);
return re;
}
void check(int tr[]){
vector<int> v;
for(int i = 0;i<n;i++)if(tr[i] != -1)v.push_back(i);
for(int i = 1;i<v.size();i++){
assert(tr[v[i-1]]<=tr[v[i]]);
assert(v[i-1] == v[i]-1);
}
return;
}
ll GO(int nn,int ss,int dd,int tarr[]){
memset(tr1,-1,sizeof(tr1));
memset(tr2,-1,sizeof(tr2));
n = nn,s = ss,d = dd;
for(int i = 0;i<n;i++)arr[i] = tarr[i];
ll ans = 0;
for(int i = s;i<min(s+d,n);i++)ans = max(ans,calc(i));
check(tr1);
check(tr2);
return ans;
}
}
#define pii pair<int,int>
#define fs first
#define sc second
namespace DC{
const int mxn = 1e5+10;
ll arr[mxn];
int n,s,d;
vector<int> v1,v2;
void dc1(int tl,int tr,int l,int r){
//todo
}
void dc2(int tl,int tr,int l,int r){
//todo
}
ll GO(int nn,int ss,int dd,int tarr[]){
n = nn,s = ss,d = dd;
for(int i= 0;i<n;i++)arr[i] = tarr[i];
for(int i = s;i<n;i++){
if((i-s)*2<=d)v1.push_back(i);
if(i-s<=d)v2.push_back(i);
}
dc1(0,s,0,v1.size()-1);
dc2(0,s,0,v2.size()-1);
return -1;
}
}
namespace MLE{
const int mxn = 2e6+10;
ll sum[mxn];
int tmp[mxn];
int ls[mxn],rs[mxn];
ll GO(){
int re = 0;
for(int i = 0;i<mxn;i++){
sum[i] = rand();
ls[i] = rand();
tmp = rand();
rs[i] = rand();
re += (sum[i]&ls[i]^rs[i]);
}
return re;
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
/*
auto t1 = BRUTE::GO(n,start,d,attraction),t2 = ZERO::GO(n,start,d,attraction);
cerr<<t1<<','<<t2<<endl;
assert(t1 == t2);
*/
return MLE::GO();
return DC::GO(n,start,d,attraction);
if(start == 0)return ZERO::GO(n,start,d,attraction);
else return BRUTE::GO(n,start,d,attraction);
}