Submission #385933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
385933	2021-04-05T09:01:08 Z	peijar	Sailing Race (CEOI12_race)	C++17	30 / 100	3000 ms	23204 KB

race

#include <bits/stdc++.h>
#define int long long
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

30.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	1 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	21 ms	748 KB	Output isn't correct
7	Correct	96 ms	1004 KB	Output is correct
8	Incorrect	25 ms	1004 KB	Output isn't correct
9	Correct	119 ms	1388 KB	Output is correct
10	Correct	350 ms	1900 KB	Output is correct
11	Correct	194 ms	1644 KB	Output is correct
12	Incorrect	750 ms	5304 KB	Output isn't correct
13	Incorrect	1531 ms	10564 KB	Output isn't correct
14	Execution timed out	3067 ms	18000 KB	Time limit exceeded
15	Execution timed out	3058 ms	14088 KB	Time limit exceeded
16	Execution timed out	3089 ms	12696 KB	Time limit exceeded
17	Execution timed out	3090 ms	14132 KB	Time limit exceeded
18	Execution timed out	3084 ms	23204 KB	Time limit exceeded
19	Execution timed out	3082 ms	11628 KB	Time limit exceeded
20	Execution timed out	3034 ms	11604 KB	Time limit exceeded