Submission #385935

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
385935	2021-04-05T09:02:40 Z	peijar	Sailing Race (CEOI12_race)	C++17	35 / 100	3000 ms	23692 KB

race

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

const int MAXN = 500;
map<pair<int, int>, int> dp;
vector<int> adj[MAXN];
int nbBateaux;

int solve(int curPos, int nbRestants)
{
	if (dp.count(make_pair(curPos, nbRestants)))
		return dp[make_pair(curPos, nbRestants)];
	int &x = dp[make_pair(curPos, nbRestants)];
	if (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);

	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	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	364 KB	Output isn't correct
3	Incorrect	2 ms	364 KB	Output isn't correct
4	Incorrect	5 ms	492 KB	Output isn't correct
5	Correct	14 ms	620 KB	Output is correct
6	Incorrect	18 ms	748 KB	Output isn't correct
7	Correct	85 ms	1004 KB	Output is correct
8	Incorrect	25 ms	1004 KB	Output isn't correct
9	Correct	125 ms	1516 KB	Output is correct
10	Correct	410 ms	1600 KB	Output is correct
11	Correct	198 ms	1644 KB	Output is correct
12	Incorrect	738 ms	5100 KB	Output isn't correct
13	Incorrect	1503 ms	10732 KB	Output isn't correct
14	Correct	2886 ms	17808 KB	Output is correct
15	Execution timed out	3064 ms	13448 KB	Time limit exceeded
16	Execution timed out	3079 ms	12524 KB	Time limit exceeded
17	Execution timed out	3077 ms	13392 KB	Time limit exceeded
18	Execution timed out	3077 ms	23692 KB	Time limit exceeded
19	Execution timed out	3077 ms	11236 KB	Time limit exceeded
20	Execution timed out	3087 ms	11032 KB	Time limit exceeded