Submission #59284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59284	2018-07-21T11:51:32 Z	MatheusLealV	Sailing Race (CEOI12_race)	C++17	0 / 100	368 ms	6348 KB

race

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

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

vector<int> grafo[N];

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

	if(l > r) return 0;

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

	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] = 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	4216 KB	Output isn't correct
2	Incorrect	6 ms	4324 KB	Output isn't correct
3	Incorrect	6 ms	4400 KB	Output isn't correct
4	Incorrect	7 ms	4604 KB	Output isn't correct
5	Incorrect	6 ms	4664 KB	Output isn't correct
6	Incorrect	6 ms	4664 KB	Output isn't correct
7	Incorrect	11 ms	4664 KB	Output isn't correct
8	Incorrect	9 ms	4664 KB	Output isn't correct
9	Incorrect	10 ms	4664 KB	Output isn't correct
10	Incorrect	22 ms	4668 KB	Output isn't correct
11	Incorrect	11 ms	4668 KB	Output isn't correct
12	Incorrect	25 ms	4724 KB	Output isn't correct
13	Incorrect	37 ms	4724 KB	Output isn't correct
14	Incorrect	86 ms	4732 KB	Output isn't correct
15	Incorrect	174 ms	5244 KB	Output isn't correct
16	Incorrect	257 ms	5720 KB	Output isn't correct
17	Incorrect	196 ms	5720 KB	Output isn't correct
18	Incorrect	81 ms	5720 KB	Output isn't correct
19	Incorrect	368 ms	6112 KB	Output isn't correct
20	Incorrect	340 ms	6348 KB	Output isn't correct