Submission #397959

#	Time	Username	Problem	Language	Result	Execution time	Memory
397959		prvocislo	Holiday (IOI14_holiday)	C++17	7 / 100	58 ms	65540 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(d + 2, 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);
	for (int t = 0; t < d; t++) for (int i = 0; i < n; i++)
	{
		upd(dp[t + 1][i], dp[t][i]);
		if (i <= s && i)
		{
			upd(dp[t + 1][i - 1], dp[t][i]);
			upd(dp[t + 2][i - 1], dp[t][i] + a[i - 1]);
		}
		if (i >= s && i + 1 < n)
		{
			upd(dp[t + 1][i + 1], dp[t][i]);
			upd(dp[t + 2][i + 1], dp[t][i] + a[i + 1]);
		}
	}
	for (int t = 0; t <= d; t++) for (int i = 0; i < n; i++)
	{
		//cout << dp[t][i] << " \n"[i == n - 1];
		if (i < s)
			upd(lf[t + abs(i - s)], dp[t][i]);
		if (i > s)
			upd(ri[t + abs(i - s)], dp[t][i]);
		upd(ans, dp[t][i]);
	}
	for (int vis = 0; vis < 2; vis++) for (int t = 0; t + vis <= d; t++) for (int i = 0; i < n; i++)
	{
		if (i < s)
			upd(ans, dp[t][i] + ri[d - t - vis] + vis * a[s]);
		if (i > s)
			upd(ans, dp[t][i] + lf[d - t - vis] + vis * a[s]);
	}
	return ans;
}

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