Submission #83360

#	Time	Username	Problem	Language	Result	Execution time	Memory
83360		farukkastamonuda	Holiday (IOI14_holiday)	C++14	100 / 100	735 ms	13324 KiB

holiday

#include "holiday.h"
#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;
//~ }

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53