Submission #385936

#	Time	Username	Problem	Language	Result	Execution time	Memory
385936		peijar	Sailing Race (CEOI12_race)	C++17	35 / 100	552 ms	2668 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;
const int DELTA = 500;
int dp[MAXN][2 * MAXN+ 10];
vector<int> adj[MAXN];
int nbBateaux;

int solve(int curPos, int nbRestants)
{
	int &x = dp[curPos][nbRestants + DELTA];
	if (x != -1) return x;
	if (abs(nbRestants) == 1)
		return x = 0;
	
	for (int prochain : adj[curPos])
	{
		if (nbRestants > 0)
		{
			if (prochain < curPos)
			{
				if (prochain + nbBateaux - curPos < nbRestants)
				{
					x = max(x, 1+solve(prochain, (curPos + nbRestants - prochain - nbBateaux)));
					x = max(x, 1+solve(prochain, -(prochain + nbBateaux - curPos)));
				}
			}
			else
			{
				if (prochain - curPos < nbRestants)
				{
					x = max(x, 1+solve(prochain, curPos + nbRestants - prochain));
					x = max(x, 1+solve(prochain, -(prochain - curPos)));
				}
			}
		}
		else
		{
			if (prochain < curPos)
			{
				if (curPos - prochain < -nbRestants)
				{
					x = max(x, 1+solve(prochain, curPos - prochain));
					x = max(x, 1+solve(prochain, -(prochain - (curPos + nbRestants))));
				}
			}
			else
			{
				if (curPos + nbBateaux - prochain < -nbRestants)
				{
					x = max(x, 1+solve(prochain, nbBateaux - prochain + curPos));
					x = max(x, 1+solve(prochain, -(-nbRestants - (nbBateaux - prochain + curPos))));
				}
			}
		}
	}
	return x;
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for (int i(0); i < MAXN; ++i)
		for (int j(0); j < 2 * MAXN + 10; ++j)
			dp[i][j] = -1;

	int type;
	cin >> nbBateaux >> type;
	for (int iBateau = 0; iBateau < nbBateaux; ++iBateau) 
	{
		int x;
		cin >> x;
		while (x)
		{
			x--;
			adj[iBateau].push_back(x);
			cin >> x;
		}
	}
	int bst(0);
	for (int iBateau(1); iBateau < nbBateaux; ++iBateau)
		if (solve(iBateau, nbBateaux) > solve(bst, nbBateaux))
			bst = iBateau;
	cout << solve(bst, nbBateaux) << endl << bst+1 << endl;
}

• Subtask 1: 35 / 100