제출 #385935

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

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