Submission #586439

#	Time	Username	Problem	Language	Result	Execution time	Memory
586439		Red_Inside	Holiday (IOI14_holiday)	C++17	7 / 100	133 ms	1676 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()

const int maxn = 7e3+100;

//#define int ll
#define pii pair <int, int>
int inf = 1e9;

ll a[3010], dp[3][7510][5], dl[7510][3], dr[7510][3];

long long int findMaxAttraction(int n, int start, int d, int attraction[]) 
{
	ll ans = 0;
	ll s = 0;
	forn(1, i, n)
	{
		a[i] = attraction[i - 1];
	}
	start++;
	forn(0, i, 1)
	{
		forn(0, j, d + 2)
		{
			forn(0, k, 3) dp[i][j][k] = -inf;
		}
	}
	int p = 0;
	dp[p][0][0] = 0;
	dp[p][1][0] = a[start];
	forn(start, i, n)
	{
		forn(0, j, d)
		{
			dr[j][0] = max(dr[j][0], dp[p][j][0]);
			dp[p ^ 1][j + 1][0] = max(dp[p ^ 1][j + 1][0], dp[p][j][0]);
			dp[p ^ 1][j + 2][0] = max(dp[p ^ 1][j + 2][0], dp[p][j][0] + a[i + 1]);
			dp[p][j][0] = -inf;
		}
		p ^= 1;
	}
	p = 0;
	dp[p][0][1] = 0;
	dp[p][1][1] = a[start];
	forn(start, i, n)
	{
		forn(0, j, d)
		{
			dr[j][1] = max(dr[j][1], dp[p][j][1]);
			dp[p ^ 1][j + 2][1] = max(dp[p ^ 1][j + 2][1], dp[p][j][1]);
			dp[p ^ 1][j + 3][1] = max(dp[p ^ 1][j + 3][1], dp[p][j][1] + a[i + 1]);
			dp[p][j][1] = -inf;
		}
		p ^= 1;
	}
	dp[p][0][2] = 0;
	nfor(1, i, start)
	{
		forn(0, j, d)
		{
			dl[j][0] = max(dl[j][0], dp[p][j][2]);
			dp[p ^ 1][j + 1][2] = max(dp[p ^ 1][j + 1][2], dp[p][j][2]);
			dp[p ^ 1][j + 2][2] = max(dp[p ^ 1][j + 2][2], dp[p][j][2] + a[i - 1]);
			dp[p][j][2] = -inf;
		}
		p ^= 1;
	}
	dp[p][0][3] = 0;
	nfor(1, i, start)
	{
		forn(0, j, d)
		{
			dl[j][1] = max(dl[j][1], dp[p][j][3]);
			dp[p ^ 1][j + 2][3] = max(dp[p ^ 1][j + 2][3], dp[p][j][3]);
			dp[p ^ 1][j + 3][3] = max(dp[p ^ 1][j + 3][3], dp[p][j][3] + a[i - 1]);
			dp[p][j][3] = -inf;
		}
		p ^= 1;
	}
	forn(1, j, d)
	{
		dr[j][0] = max(dr[j][0], dr[j - 1][0]);
		dr[j][1] = max(dr[j][1], dr[j - 1][1]);
		dl[j][0] = max(dl[j][0], dl[j - 1][0]);
		dl[j][1] = max(dl[j][1], dl[j - 1][1]);
	}
	forn(0, j, d)
	{
		ans = max(ans, dr[j][1] + dl[d - j][0]);
		ans = max(ans, dr[j][0] + dl[d - j][1]);
		ans = max(ans, dl[j][1] + dr[d - j][0]);
		ans = max(ans, dl[j][0] + dr[d - j][1]);
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:6:11: warning: unused variable 'second' [-Wunused-variable]
    6 | #define s second
      |           ^~~~~~
holiday.cpp:24:5: note: in expansion of macro 's'
   24 |  ll s = 0;
      |     ^

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