Submission #59289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59289	2018-07-21T11:58:21 Z	MatheusLealV	Sailing Race (CEOI12_race)	C++17	40 / 100	736 ms	9952 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, 1) + 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(v, i, 0) + 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 ? opt : opt - n)<<"\n";
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:84:33: warning: unused variable 'S2' [-Wunused-variable]
     int S = solve(i, v, 1) + 1, S2 = 0;//solve(v, i + n, 0) + 1;
                                 ^~
race.cpp:95:33: warning: unused variable 'S2' [-Wunused-variable]
     int S = solve(v, i, 0) + 1, S2 = 0;//solve(i, v + n, 1) + 1;
                                 ^~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	8184 KB	Output is correct
2	Incorrect	11 ms	8300 KB	Output isn't correct
3	Incorrect	11 ms	8300 KB	Output isn't correct
4	Incorrect	10 ms	8364 KB	Output isn't correct
5	Correct	11 ms	8364 KB	Output is correct
6	Incorrect	16 ms	8364 KB	Output isn't correct
7	Correct	16 ms	8504 KB	Output is correct
8	Incorrect	10 ms	8504 KB	Output isn't correct
9	Correct	26 ms	8564 KB	Output is correct
10	Correct	36 ms	8704 KB	Output is correct
11	Correct	23 ms	8704 KB	Output is correct
12	Incorrect	47 ms	8760 KB	Output isn't correct
13	Incorrect	64 ms	8784 KB	Output isn't correct
14	Correct	127 ms	8968 KB	Output is correct
15	Incorrect	381 ms	9276 KB	Output isn't correct
16	Incorrect	491 ms	9900 KB	Output isn't correct
17	Incorrect	410 ms	9900 KB	Output isn't correct
18	Correct	140 ms	9900 KB	Output is correct
19	Incorrect	574 ms	9900 KB	Output isn't correct
20	Incorrect	736 ms	9952 KB	Output isn't correct