oj.uz

Submission #385941

# Submission time Handle Problem Language Result Execution time Memory
385941 2021-04-05T09:10:57 Z peijar Sailing Race (CEOI12_race) C++17
10 / 100
 553 ms 2816 KB 
#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 (!nbRestants)
		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-1)));
				}
			}
			else
			{
				if (prochain - curPos <= nbRestants)
				{
					x = max(x, 1+solve(prochain, curPos + nbRestants - prochain));
					x = max(x, 1+solve(prochain, -(prochain - curPos-1)));
				}
			}
		}
		else
		{
			if (prochain < curPos)
			{
				if (curPos - prochain <= -nbRestants)
				{
					x = max(x, 1+solve(prochain, curPos - prochain-1));
					x = max(x, 1+solve(prochain, -(prochain - (curPos + nbRestants))));
				}
			}
			else
			{
				if (curPos + nbBateaux - prochain < -nbRestants)
				{
					x = max(x, 1+solve(prochain, nbBateaux - prochain + curPos-1));
					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-1) > solve(bst, nbBateaux-1))
			bst = iBateau;
	cout << solve(bst, nbBateaux-1) << endl << bst+1 << endl;
}

Subtask #1
10.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 Incorrect 3 ms 2284 KB Output isn't correct
6 Incorrect 4 ms 2284 KB Output isn't correct
7 Incorrect 7 ms 2412 KB Output isn't correct
8 Incorrect 5 ms 2284 KB Output isn't correct
9 Incorrect 8 ms 2412 KB Output isn't correct
10 Correct 19 ms 2412 KB Output is correct
11 Incorrect 12 ms 2412 KB Output isn't correct
12 Incorrect 33 ms 2412 KB Output isn't correct
13 Incorrect 60 ms 2412 KB Output isn't correct
14 Incorrect 102 ms 2412 KB Output isn't correct
15 Incorrect 357 ms 2540 KB Output isn't correct
16 Incorrect 477 ms 2796 KB Output isn't correct
17 Incorrect 352 ms 2540 KB Output isn't correct
18 Incorrect 128 ms 2412 KB Output isn't correct
19 Incorrect 553 ms 2816 KB Output isn't correct
20 Incorrect 545 ms 2796 KB Output isn't correct