Submission #59285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59285	2018-07-21T11:53:30 Z	MatheusLealV	Sailing Race (CEOI12_race)	C++17	10 / 100	681 ms	9700 KB

race

#include <bits/stdc++.h>
#define N 1001
using namespace std;

int n, k, ans, opt, dp[N][N][2];

vector<int> grafo[N];

int solve(int l, int r, int f)
{
	int ans = 0;

	if(l > r) return 0;

	if(dp[l][r][f] != -1) return dp[l][r][f];

	if(f == 0)
	{
		for(auto v: grafo[l])
		{
			if(l + 1 <= v and v <= r - 1)
			{
				int aux = max(solve(l, v, 1), solve(v, r, 0)) + 1;

				ans = max(ans, aux);
			}
		}
	}

	else
	{
		for(auto v: grafo[r])
		{
			if(l + 1 <= v and v <= r - 1)
			{
				int aux = max(solve(l, v, 1), solve(v, r, 0)) + 1;

				ans = max(ans, aux);
			}
		}		
	}

	//cout<<"SOLVE "<<l<<", "<<r<<" "<<ans<<"\n";

	return dp[l][r][f] = ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>k;

	memset(dp, -1, sizeof dp);

	for(int i = 1; i <= n; i++)
	{
		while(true)
		{
			int x;

			cin>>x;

			if(!x) break;

			grafo[i].push_back(x);

			grafo[i].push_back(n + x);

			grafo[i + n].push_back(x);

			grafo[i + n].push_back(x + n);
		}
	}

	for(int i = 1; i <= 2*n; i++)
	{
		for(auto v: grafo[i])
		{
			if(abs(i - v) >= n) continue;

			if(i < v)
			{
				int S = solve(i, v, 0) + 1, S2 = 0;//solve(v, i + n, 0) + 1;

				//cout<<"AAA "<<v<<" "<<i + n<<"\n";

				if(S >= ans) ans = S, opt = i;

				if(S2 >= ans) ans = S2, opt = i;
			}

			else if(i > v)
			{
				int S = solve(i, v, 1) + 1, S2 = 0;//solve(i, v + n, 1) + 1;

				//cout<<"ff "<<v + n<<" "<<i<<"\n";

				if(S >= ans) ans = S, opt = i;

				if(S2 >= ans) ans = S2, opt = i;
			}
		}
	}

	cout<<ans<<"\n"<<opt<<"\n";
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	8184 KB	Output isn't correct
2	Incorrect	9 ms	8296 KB	Output isn't correct
3	Incorrect	9 ms	8476 KB	Output isn't correct
4	Incorrect	11 ms	8476 KB	Output isn't correct
5	Incorrect	10 ms	8476 KB	Output isn't correct
6	Incorrect	11 ms	8476 KB	Output isn't correct
7	Correct	14 ms	8476 KB	Output is correct
8	Incorrect	12 ms	8476 KB	Output isn't correct
9	Correct	19 ms	8476 KB	Output is correct
10	Incorrect	46 ms	8600 KB	Output isn't correct
11	Incorrect	21 ms	8600 KB	Output isn't correct
12	Incorrect	46 ms	8692 KB	Output isn't correct
13	Incorrect	93 ms	8692 KB	Output isn't correct
14	Incorrect	149 ms	8748 KB	Output isn't correct
15	Incorrect	622 ms	9240 KB	Output isn't correct
16	Incorrect	626 ms	9612 KB	Output isn't correct
17	Incorrect	421 ms	9612 KB	Output isn't correct
18	Incorrect	136 ms	9612 KB	Output isn't correct
19	Incorrect	655 ms	9684 KB	Output isn't correct
20	Incorrect	681 ms	9700 KB	Output isn't correct