Submission #397968

#	Time	Username	Problem	Language	Result	Execution time	Memory
397968		prvocislo	Holiday (IOI14_holiday)	C++17	24 / 100	5063 ms	13208 KiB

holiday

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

void upd(ll& a, const ll& b) { a = max(a, b); }
ll findMaxAttraction(int n, int s, int d, int a[])
{
	const ll minf = -1e18;
	vector<vector<ll> > dp(3, vector<ll>(n, minf)); 
	// ked sme v meste i tak predpokladame ze sme sa uz rozhodli ze ci sme ho navstivili
	dp[0][s] = 0; // az potom sa rozhodneme ci navstivime tuto atrakciu
	ll ans = minf;
	vector<ll> lf(d + n + 1, 0), ri(d + n + 1, 0), lf0(d + 1, 0), ri0(d + 1, 0);
	for (int t = 0; t <= d; t++)
	{
		for (int i = 0; i < n; i++)
		{
			upd(dp[1][i], dp[0][i]);
			if (i <= s && i)
			{
				upd(dp[1][i - 1], dp[0][i]);
				upd(dp[2][i - 1], dp[0][i] + a[i - 1]);
			}
			if (i >= s && i + 1 < n)
			{
				upd(dp[1][i + 1], dp[0][i]);
				upd(dp[2][i + 1], dp[0][i] + a[i + 1]);
			}
			if (i < s)
				upd(lf[t + abs(i - s)], dp[0][i]), upd(lf0[t], dp[0][i]);
			if (i > s)
				upd(ri[t + abs(i - s)], dp[0][i]), upd(ri0[t], dp[0][i]);
			upd(ans, dp[0][i]);
		}
		dp[0] = dp[1]; dp[1] = dp[2];
		for (int i = 0; i < n; i++) dp[2][i] = minf;
	}
	for (int vis = 0; vis < 2; vis++) for (int t = 0; t + vis <= d; t++)
	{
		upd(ans, lf0[t] + ri[d - t - vis] + vis * a[s]);
		upd(ans, ri0[t] + lf[d - t - vis] + vis * a[s]);
	}
	return ans;
}

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