Submission #136107

#	Time	Username	Problem	Language	Result	Execution time	Memory
136107		arthurconmy	Holiday (IOI14_holiday)	C++14	24 / 100	5017 ms	2152 KiB

holiday

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "holiday.h"
#endif
using namespace std;
using ll=long long;

ll findMaxAttraction(int n, int sta, int d, int A[])
{
	ll global_ans=0LL;

	for(int r=sta; r<n; r++)
	{
		ll ans=0LL;

		priority_queue<ll> active;
		ll active_sum=0LL;

		for(int i=sta+1; i<=r; i++)
		{
			active_sum += ll(A[i]);
			active.push(ll(-A[i]));
		}

		for(int i=sta; i>=0; i--)
		{
			active.push(ll(-A[i]));
			active_sum += ll(A[i]);

			// cout << 2*(r-sta) + sta-i << endl;

			while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
			{
				active_sum += active.top();
				active.pop();
			}

			if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
		}

		global_ans = max(global_ans,ans);

		// cout << r << " " << ans << endl;
	}

	// reverse that shit afterwards

	int B[n];

	for(int i=0; i<n; i++) B[i]=A[n-i-1];
	sta = n-sta-1;

	for(int r=sta; r<n; r++)
	{
		ll ans=0LL;

		priority_queue<ll> active;
		ll active_sum=0LL;

		for(int i=sta+1; i<=r; i++)
		{
			active_sum += ll(B[i]);
			active.push(ll(-B[i]));
		}

		for(int i=sta; i>=0; i--)
		{
			active.push(ll(-B[i]));
			active_sum += ll(B[i]);

			// cout << 2*(r-sta) + sta-i << endl;

			while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
			{
				active_sum += active.top();
				active.pop();
			}

			if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
		}

		global_ans = max(global_ans,ans);

		// cout << r << " " << ans << endl;
	}

	return global_ans;
}

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