oj.uz

답안 #385936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385936 2021-04-05T09:05:16 Z peijar Sailing Race (CEOI12_race) C++17
35 / 100
 552 ms 2668 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 (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

# 결과 실행 시간 메모리 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