Submission #61044

#	Time	Username	Problem	Language	Result	Execution time	Memory
61044		hamzqq9	Holiday (IOI14_holiday)	C++14	100 / 100	842 ms	10912 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define ll long long
#define N 100005
#define orta ((bas+son)>>1)

int Left,Right,n,d,totD,start;
int pos[N];
ll dp[N];
pair<ll,int> attr[N];

struct  SEG {
	
	int ok;
	ll sum;

}S[N*4];

SEG merge(SEG A,SEG B) {

	return {A.ok+B.ok,A.sum+B.sum};

}

ll get(int node,int bas,int son,int val) {

	if(bas==son) return (val>0)*S[node].sum;

	if(S[node*2].ok>val) return get(node*2,bas,orta,val);
	else return get(node*2+1,orta+1,son,val-S[node*2].ok)+S[node*2].sum;

}

void up(int node,int bas,int son,int x,int val) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		S[node].ok=val;
		S[node].sum=val*attr[bas].st;

		return ;

	}

	up(node*2,bas,orta,x,val);
	up(node*2+1,orta+1,son,x,val);

	S[node]=merge(S[node*2],S[node*2+1]);

}

void up_it() {

	totD=Right-Left+min(start-Left,Right-start);

}

void moveR(int val) {

	while(Right<val) {

		Right++;

		up(1,0,n-1,pos[Right],1);

	}

	while(Right>val) {

		up(1,0,n-1,pos[Right],0);

		Right--;

	}

	up_it();

}

void moveL(int val) {

	while(Left<val) {

		up(1,0,n-1,pos[Left],0);

		Left++;

	}

	while(Left>val) {

		Left--;

		up(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;
	ll ans=-1;

	for(int i=pbas;i<=pson;i++) {

		moveR(i);

		if(totD>d) break ;

		int rem=d-totD;

		ll res=get(1,0,n-1,min(rem,S[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[]) {

	ll ans=0;

	::n=n;
	::d=d;
	::start=start;

	for(int i=0;i<n;i++) attr[i]={attraction[i],i};

	sort(attr,attr+n,greater< pair<ll,int> >());

	for(int i=0;i<n;i++) pos[attr[i].nd]=i;

	Right=start-1;
	Left=start+1;

	solve(0,start,start,n-1);

	for(int i=0;i<=start;i++) ans=max(ans,dp[i]);
	
	return ans;

}

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