Submission #168571

#	Time	Username	Problem	Language	Result	Execution time	Memory
168571		johutha	Holiday (IOI14_holiday)	C++14	0 / 100	5022 ms	6380 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 -1;
		if (lstart + ceil((double)d / 2.0) > n)
		{
			int cres = 0;
			for (int i = lstart; i < n; i++) cres += attraction[i];
			return cres;
		}

		multiset<int> used;

		int cres = 0;

		int pos;

		for (pos = lstart; pos < lstart + ceil((double)d / 2.0); pos++)
		{
			cres += attraction[pos];
			used.insert(attraction[pos]);
		}

		if (d % 2)
		{
			cres -= *used.begin();
			used.erase(used.begin());
		}

		int mmax = cres;

		for (; pos < n; pos++)
		{
			if (used.size() < 2) break;
			cres -= *used.begin();
			used.erase(used.begin());
			cres -= *used.begin();
			used.erase(used.begin());

			cres += attraction[pos];
			used.insert(attraction[pos]);

			mmax = max(mmax, cres);
		}

		return mmax;
	}

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

		return mmax;
	}
};

int findMaxAttraction(signed n, signed start, signed d, signed attraction[])
{
    Attractions at;
	at.n = n;
	at.start = start;
	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