Submission #59289

#	Time	Username	Problem	Language	Result	Execution time	Memory
59289		MatheusLealV	Sailing Race (CEOI12_race)	C++17	40 / 100	736 ms	9952 KiB

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 (stderr)

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