Submission #203392

#	Time	Username	Problem	Language	Result	Execution time	Memory
203392		oolimry	Holiday (IOI14_holiday)	C++14	100 / 100	2140 ms	7160 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

long long n, start, days;
long long arr[100005];
long long opt[100005];
bool taken[100005];
long long ans = 0;

multiset<long long> take;
multiset<long long> notake;
long long value = 0;
long long canTake;

void include(long long pos){
	taken[pos] = true;
	if(pos > start) canTake--;
	else if(pos < start) canTake -= 2;
	
	take.insert(arr[pos]);
	value += arr[pos];
	
	while((long long) take.size() > max(canTake,0LL)){
		multiset<long long>::iterator it = take.begin();
		value -= *it;
		notake.insert(*it);
		take.erase(it);
	}
	
	//cout << "Include "  << pos << ": " << value << " " << canTake << " " << take.size() << " " << notake.size() << endl;
}

void exclude(long long pos){
	
	taken[pos] = false;
	
	if(pos > start) canTake++;
	else if(pos < start) canTake += 2;
	
	if(take.find(arr[pos]) != take.end()){
		take.erase(take.find(arr[pos]));
		value -= arr[pos];
	}
	else if(notake.find(arr[pos]) != notake.end()){
		notake.erase(notake.find(arr[pos]));
	}
	else{
		assert(false);
	}
	while((long long) take.size() < canTake){
		if(notake.empty()) break;
		multiset<long long, greater<long long> >::iterator it = (--notake.end());
		value += *it;
		take.insert(*it);
		notake.erase(it);
	}
	
	//cout << "Exclude "  << pos << ": " << value << " " << canTake << " " << take.size() << " " << notake.size() << endl;
}

void reset(){
	fill(taken,taken+(n+1),false);
	take.clear();
	notake.clear();
	value = 0;
	canTake = days;
	include(start);
}

void solve(){
	fill(opt,opt+(n+1),-1);
	opt[0] = start;
		
	for(long long bit = (1<<17);bit > 0;bit >>= 1){
		if(bit > start) continue;
		
		reset();
		for(long long i = bit;i < start;i++){
			include(i);
		}
		
		long long R = start + 1; ///next value not taken
		
		for(long long L = bit;L <= start;L += 2 * bit){
			//cout << L << "\n";
			
			long long endPoint;
			if(L + bit <= start) endPoint = opt[L + bit];
			else endPoint = n;
			
			long long best = value;
			long long bestR = opt[L - bit];
			
			while(R <= endPoint){
				include(R);
				if(best < value){
					best = value;
					bestR = R;
				}
				R++;
			}
			
			opt[L] = bestR;
			
			//cout << L << " " << opt[L] << " " << best << "\n";
			ans = max(ans, best);
			
			for(long long i = L;i < min(start, L + 2 * bit);i++){
				exclude(i);
			}
		}
	}
}

long long findMaxAttraction(int N, int START, int DAYS, int ARR[]) {
	n = N;
	for(long long i = 0;i < n;i++) arr[i+1] = ARR[i];
	start = START + 1;
	days = DAYS;
	
	reset();
	solve();
	
	
	reverse(arr+1,arr+(n+1));
	start = n - start + 1;
	reset();
	solve();
	
	
    return ans;
}

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