Submission #420794

#	Time	Username	Problem	Language	Result	Execution time	Memory
420794		faresbasbs	Holiday (IOI14_holiday)	C++14	47 / 100	5095 ms	6912 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
vector<long long> in;
long long n,d,start;

void r(){
	reverse(in.begin(),in.end()) , start = n-start-1;
}

long long solve3(){
	long long d2 = d-1 , ret = in[start] , sum = ret;
	multiset<long long> ms;
	ms.insert(in[start]);
	for(long long i = start+1 ; i < n ; i += 1){
		d2 -= 1;
		if(d2 < 0){
			d2 += 1;
			if(ms.size() == 0){
				return ret;
			}
			sum -= *ms.begin();
			ms.erase(ms.begin());
		}
		if(d2){
			d2 -= 1;
			sum += in[i];
			ms.insert(in[i]);
		}else if(ms.size() && in[i] > *ms.begin()){
			sum -= *ms.begin();
			ms.erase(ms.begin());
			sum += in[i];
			ms.insert(in[i]);
		}
		ret = max(ret,sum);
	}
	return ret;
}

long long solve2(){
	long long ret = solve3();
	r();
	ret = max(ret,solve3());
	r();
	return ret;
}

long long solve(){
	long long ret = 0;
	for(long long l = 0 ; l < start ; l += 1){
		if(2*(start-l) > d){
			continue;
		}
		long long d2 = d-2*(start-l) , sum = 0;
		multiset<long long> ms;
		for(long long i = l ; i <= start ; i += 1){
			if(d2){
				d2 -= 1;
				sum += in[i];
				ms.insert(in[i]);
			}else if(ms.size() && in[i] > *ms.begin()){
				sum -= *ms.begin();
				ms.erase(ms.begin());
				sum += in[i];
				ms.insert(in[i]);
			}
			ret = max(ret,sum);
		}
		for(long long i = start+1 ; i < n ; i += 1){
			if(ms.size() == 0 && d2 == 0){
				break;
			}
			d2 -= 1;
			if(d2 < 0){
				d2 += 1;
				sum -= *ms.begin();
				ms.erase(ms.begin());
			}
			if(d2){
				d2 -= 1;
				sum += in[i];
				ms.insert(in[i]);
			}else if(ms.size() && in[i] > *ms.begin()){
				sum -= *ms.begin();
				ms.erase(ms.begin());
				sum += in[i];
				ms.insert(in[i]);
			}
			ret = max(ret,sum);
		}
	}
	return ret;
}

long long int findMaxAttraction(int N , int Start , int D , int attraction[]){
	n = N , start = Start , d = D;
	if(d == 0){
		return 0;
	}
	for(int i = 0 ; i < n ; i += 1){
		in.push_back(attraction[i]);
	}
	long long ret = solve2();
	if(start == 0){
		return ret;
	}
	ret = max(ret,solve());
	r();
	ret = max(ret,solve());
	return ret;
}

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