Submission #446602

#	Time	Username	Problem	Language	Result	Execution time	Memory
446602		ArianKheirandish	Sailing Race (CEOI12_race)	C++17	35 / 100	506 ms	5072 KiB

race

//in the name of god//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)		x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair

const int maxn = 500 + 10;
const int LG = 30;
const ll Inf = 1e9 + 10;
int n, k;
int dp[maxn][maxn][2][2];
vector <int> g[maxn];
bool c[maxn][maxn];

int Sol(int l, int r, int d, int x){
	int &ans = dp[l][r][d][x];
	if(ans != -1)
		return ans;
		
	ans = 0;
	if(l == r)
		return ans;
	
	int v = (!x ? l : r);
	if(!d){
		for(auto i : g[v])
			if(i > l && i < r)
				ans = max(ans, 1 + Sol(l, i, d, 1)),
				ans = max(ans, 1 + Sol(i, r, d, 0));
	}
	else{
		for (auto i : g[v])
			if (i < l)
				ans = max(ans, 1 + Sol(i, l, 0, 0)),
				ans = max(ans, 1 + Sol(i, r, d, 0));
			else if (i > r)
				ans = max(ans, 1 + Sol(l, i, d, 1)),
				ans = max(ans, 1 + Sol(r, i, !d, 1));
	}
	return ans;
}

int main(){_
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++){
		while(true){
			int x;
			cin >> x;
			if(x == 0)
				break;
			g[i].push_back(x);
			c[i][x] = 1;
		}
	}
	
	int ans = 0, bst = 0;
	memset(dp, -1, sizeof dp);
	for(int l = 1 ; l <= n ; l ++)
		for(int r = l + 1 ; r <= n ; r ++){
			int a = Sol(l, r, 0, 0);
			int b = Sol(l, r, 1, 0);
			int C = Sol(l, r, 0, 1);
			int d = Sol(l, r, 1, 1);
			
			if(c[l][r] && 1 + C > ans)
				ans = 1 + C, bst = r;
			if(c[l][r] && 1 + d > ans)
				ans = 1 + d, bst = r;
			if(c[r][l] && 1 + a > ans)
				ans = 1 + a, bst = r;
			if(c[r][l] && 1 + b > ans)
				ans = 1 + b, bst = r;
		}
	cout << ans << '\n' << bst << '\n';
	return 0;
}

• Subtask 1: 35 / 100