oj.uz

Submission #59287

# Submission time Handle Problem Language Result Execution time Memory
59287 2018-07-21T11:56:35 Z MatheusLealV Sailing Race (CEOI12_race) C++17
30 / 100
 647 ms 10348 KB 
#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(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";
}

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(i, v, 1) + 1, S2 = 0;//solve(i, v + n, 1) + 1;
                                 ^~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8184 KB Output isn't correct
2 Incorrect 9 ms 8300 KB Output isn't correct
3 Incorrect 10 ms 8380 KB Output isn't correct
4 Incorrect 10 ms 8380 KB Output isn't correct
5 Correct 12 ms 8380 KB Output is correct
6 Incorrect 10 ms 8380 KB Output isn't correct
7 Correct 16 ms 8464 KB Output is correct
8 Incorrect 11 ms 8500 KB Output isn't correct
9 Correct 22 ms 8548 KB Output is correct
10 Incorrect 47 ms 8688 KB Output isn't correct
11 Correct 20 ms 8688 KB Output is correct
12 Incorrect 40 ms 8688 KB Output isn't correct
13 Incorrect 68 ms 8760 KB Output isn't correct
14 Correct 111 ms 8832 KB Output is correct
15 Incorrect 465 ms 9276 KB Output isn't correct
16 Incorrect 647 ms 9896 KB Output isn't correct
17 Incorrect 421 ms 9896 KB Output isn't correct
18 Correct 165 ms 9896 KB Output is correct
19 Incorrect 578 ms 10312 KB Output isn't correct
20 Incorrect 594 ms 10348 KB Output isn't correct