제출 #385941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385941		peijar	Sailing Race (CEOI12_race)	C++17	10 / 100	553 ms	2816 KiB

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 (!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 / 100