Submission #385936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
385936	2021-04-05T09:05:16 Z	peijar	Sailing Race (CEOI12_race)	C++17	35 / 100	552 ms	2668 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2284 KB	Output is correct
2	Incorrect	2 ms	2284 KB	Output isn't correct
3	Incorrect	2 ms	2284 KB	Output isn't correct
4	Incorrect	3 ms	2284 KB	Output isn't correct
5	Correct	3 ms	2304 KB	Output is correct
6	Incorrect	3 ms	2284 KB	Output isn't correct
7	Correct	6 ms	2284 KB	Output is correct
8	Incorrect	4 ms	2284 KB	Output isn't correct
9	Correct	8 ms	2284 KB	Output is correct
10	Correct	18 ms	2412 KB	Output is correct
11	Correct	12 ms	2284 KB	Output is correct
12	Incorrect	33 ms	2412 KB	Output isn't correct
13	Incorrect	61 ms	2540 KB	Output isn't correct
14	Correct	104 ms	2412 KB	Output is correct
15	Incorrect	364 ms	2532 KB	Output isn't correct
16	Incorrect	458 ms	2668 KB	Output isn't correct
17	Incorrect	358 ms	2412 KB	Output isn't correct
18	Incorrect	129 ms	2412 KB	Output isn't correct
19	Incorrect	552 ms	2648 KB	Output isn't correct
20	Incorrect	549 ms	2540 KB	Output isn't correct