Submission #15841

#	Time	Username	Problem	Language	Result	Execution time	Memory
15841		myungwoo	Holiday (IOI14_holiday)	C++14	30 / 100	4873 ms	3152 KiB

holiday

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

#define MAXN 100005
typedef long long lld;

static int N, S, T;
static int A[MAXN];

lld proc()
{
	lld ret = 0;
	for (int i=S;i;i--){
		priority_queue <int> que;
		lld sum = 0;
		int left = T;
		for (int j=S;j>=i;j--){
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
			sum += A[j];
			ret = max(ret, sum);
			que.push(-A[j]);
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
		}
		while (left < S-i){
			if (que.empty()) break;
			sum += que.top(); que.pop();
			left++;
		}
		if (left < S-i) break;
		left -= S-i;
		for (int j=S+1;j<=N;j++){
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
			sum += A[j];
			ret = max(ret, sum);
			que.push(-A[j]);
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
		}
	}
	return ret;
}

lld findMaxAttraction(int n, int start, int d, int arr[])
{
	N = n, S = start+1, T = d;
	for (int i=1;i<=N;i++) A[i] = arr[i-1];
	lld ret = proc();
	if (S) return ret;
	reverse(A+1, A+N+1); S = N-S+1;
	return max(ret, proc());
}

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