oj.uz

답안 #59285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59285 2018-07-21T11:53:30 Z MatheusLealV Sailing Race (CEOI12_race) C++17
10 / 100
 681 ms 9700 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, 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

# 결과 실행 시간 메모리 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