Submission #168576

#	Time	Username	Problem	Language	Result	Execution time	Memory
168576		johutha	Holiday (IOI14_holiday)	C++14	0 / 100	5081 ms	4060 KiB

holiday

#include"holiday.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <cmath>

#define int long long

using namespace std;

struct Attractions
{
	int n, totd;
	int start;
	vector<int> attraction;

	int findMaxAttr(int lstart, int d)
	{
		if (d <= 0) return 0;
		multiset<int> active;
		int cres = 0;
		int pos;
		for (pos = lstart; pos < lstart + d/2; pos++)
		{
			if (pos >= n) return cres;
			cres += attraction[pos];
			active.insert(attraction[pos]);
		}

		if (pos == n) return cres;
		if (d % 2)
		{
			cres += attraction[pos];
			active.insert(attraction[pos]);
			pos++;
		}

		/*for (int i : active) cerr << i << " ";
		cerr << "\n";
		cerr << pos << "\n";*/

		if (d % 2 == 0)
		{
			cres += attraction[pos];
			active.insert(attraction[pos]);
			cres -= *active.begin();
			active.erase(active.begin());
			pos++;
		}

		int mmax = cres;

		for (; pos < n; pos++)
		{
			if (active.size() < 1) break;
			cres += attraction[pos];
			active.insert(attraction[pos]);
			cres -= *active.begin();
			active.erase(active.begin());
			cres -= *active.begin();
			active.erase(active.begin());
			mmax = max(mmax, cres);
		}

		return mmax;
	}

	int solve()
	{
		int mmax = 0;

		for (int i = 0; i <= start; i++)
		{
			mmax = max(mmax, findMaxAttr(i, totd - start + i));
		}

		if (start == 0) return mmax;

		reverse(attraction.begin(), attraction.end());
		start = n - start - 1;

		for (int i = 0; i <= start; i++)
		{
			mmax = max(mmax, findMaxAttr(i, totd - start + i));
		}

		return mmax;
	}
};

int findMaxAttraction(signed n, signed start, signed d, signed attraction[])
{
    Attractions at;
	at.n = n;
	at.start = start + n;
	at.totd = d;

	for (int i = 0; i < n; i++)
	{
		at.attraction.push_back(attraction[i]);
	}

	return at.solve();
}

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