| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 83359 | farukkastamonuda | Holiday (IOI14_holiday) | C++14 | 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>
#define li 100005
#define inf 2000001000
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ii pair<lo int,lo int>
#define orta (bas+son)/2
#define mid (start+end)/2
using namespace std;
int Left,Right,n,d,start,pos[li],totD,g[105];
lo int dp[li];
pair<lo int, int> at[li];
struct SEG{
int ok;
lo int sum;
}tree[li*4];
SEG merge(SEG a,SEG b){
return {a.ok+b.ok,a.sum+b.sum};
}
lo int get(int node,int start,int end,int val){
if(start==end) return (val>0)*tree[node].sum;
if(tree[node*2].ok>val){
return get(node*2,start,mid,val);
}
else return get(node*2+1,mid+1,end,val-tree[node*2].ok)+tree[node*2].sum;
}
void update(int node,int start,int end,int x,int val){
if(start>end || start>x || end<x) return ;
if(start==x && end==x){
tree[node].ok=val;
tree[node].sum=val*at[start].fi;
return ;
}
update(node*2,start,mid,x,val),update(node*2+1,mid+1,end,x,val);
tree[node]=merge(tree[node*2],tree[node*2+1]);
}
void up_it(){
totD=Right-Left+min(start-Left,Right-start);
}
void moveR(int x){
while(Right<x){
Right++;
update(1,0,n-1,pos[Right],1);
}
while(Right>x){
update(1,0,n-1,pos[Right],0);
Right--;
}
up_it();
}
void moveL(int x){
while(Left<x){
update(1,0,n-1,pos[Left],0);
Left++;
}
while(Left>x){
Left--;
update(1,0,n-1,pos[Left],1);
}
up_it();
}
void solve(int bas,int son,int pbas,int pson){
if(bas>son) return ;
moveL(orta);
int tutP=pbas;
lo int ans=-1;
for(int i=pbas;i<=pson;i++){
moveR(i);
if(totD>d) break;
int rem=d-totD;
lo int res=get(1,0,n-1,min(rem,tree[1].ok));
if(res>=ans){
ans=res;
tutP=i;
}
}
dp[orta]=ans;
solve(bas,orta-1,pbas,tutP),solve(orta+1,son,tutP,pson);
}
long long int findMaxAttraction(int n,int start,int d,int attraction[]){
::n=n;
::d=d;
::start=start;
lo int ans=0;
for(int i=0;i<n;i++) at[i]=mp(attraction[i],i);
sort(at,at+n,greater< pair<lo int,int> >());
for(int i=0;i<n;i++) pos[at[i].se]=i;
Left=start+1;
Right=start-1;
solve(0,start,start,n-1);
for(int i=0;i<=start;i++) ans=max(ans,dp[i]);
return ans;
}
int main(){
g[0]=10,g[1]=2,g[2]=20,g[3]=30,g[4]=1;
lo int ty=findMaxAttraction(5,2,7,g);
printf("%lld\n",ty);
return 0;
}