Submission #134609

#	Time	Username	Problem	Language	Result	Execution time	Memory
134609		mirbek01	Holiday (IOI14_holiday)	C++11	24 / 100	5070 ms	3400 KiB

holiday

#include "holiday.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

int d, start;
long long ans;
vector <int> vec, a;

void calc(int l, int r, int opl, int opr){
	if(l > r) return ;
	int md = (l + r) >> 1, opt = -1;
	long long ret = -1;
	for(int i = opl; i <= opr; i ++){
		int lenA = (start - md), lenB = (i - start);
		int cnt = d - lenA - lenB - min(lenA, lenB);
		vector <int> vc;
		for(int k = md; k <= i; k ++)
			vc.push_back(vec[a[k]]);
		sort(vc.rbegin(), vc.rend());
		long long now = 0;
		for(int k = 0; k < min( (int)vc.size(), cnt ); k ++)
			now += vc[k];
		if(ret < now){
			ret = now;
			opt = i;
		}
	}
	ans = max(ans, ret);
	calc(l, md - 1, opl, opt);
	calc(md + 1, r, opt, opr);
}

long long int findMaxAttraction(int n, int startS, int D, int ar[]) {
	d = D;
	start = startS;
	vec.push_back(-2e9);
	for(int i = 0; i < n; i ++){
		vec.push_back(ar[i]);
	}
	sort(vec.begin(),vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	for(int i = 0; i < n; i ++){
		ar[i] = lower_bound(vec.begin(),vec.end(), ar[i])-vec.begin();
		a.push_back(ar[i]);
	}
	calc(0, start, start, n);
	return ans;
}

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