Submission #446607

#	Time	Username	Problem	Language	Result	Execution time	Memory
446607		ArianKheirandish	Sailing Race (CEOI12_race)	C++17	40 / 100	3096 ms	4812 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 int Inf = 1e9 + 10;
int n, k;
int dp[maxn][maxn][2], dp1[maxn][maxn][2];
vector <int> g[maxn];
bool c[maxn][maxn];
int ans[maxn];

int nxt(int x){
	return (x == 1) ? n : x - 1;
}

int prv(int x){
	return (x == n) ? 1 : x + 1;
}

int Sol(int l, int r, int x){
	int &anss = dp[l][r][x];
	if(anss != -1)
		return anss;
		
	anss = 0;
	if(x){
		for(int i = nxt(l) ; i != r ; i = nxt(i))
			if(c[r][i])
				anss = max(anss, 1 + Sol(l, i, 1)),
				anss = max(anss, 1 + Sol(r, i, 0));
	}
	else{
		for(int i = prv(l) ; i != r ; i = prv(i))
			if(c[r][i])		
				anss = max(anss, 1 + Sol(l, i, 0)),
				anss = max(anss, 1 + Sol(r, i, 1));		
	}
	return anss;
}

int mx, bst;
int Solv(int l, int r, int x){
	if(l == r)
		return 0;
	
	int &anss = dp[l][r][x];
	if(anss != -1)
		return anss;
	
	anss = -1 * Inf;	
	if(x){
		for (int i = nxt(l) ; 1 ; i = nxt(i)){
			if (c[l][i])
				anss = max(anss, 1 + Solv(i, r, 1));
			if(i == r)
				break;
		}
	}
	else{
		for (int i = nxt(l) ; 1 ; i = nxt(i)){
			if (c[l][i])
				anss = max(anss, 1 + Solv(i, r, 0));
			if(i == r)
				break;
		}
	}
	return anss;
}

bool chk1(int z, int l, int r){
	if(l <= r)
		return !(l <= z && z <= r);
		
	swap(l, r);
	return (l < z && z < r);
}

bool chk2(int z, int l, int r){
	if(l <= r)
		return 	(l < z && z < r);
	swap(l, r);
	return !(l <= z && z <= r);	
}

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;
		}
	}
	
	memset(dp, -1, sizeof(dp));
	for(int l = 1; l <= n; l ++)
		for(int r = 1; r <= n; r ++){
			Sol(r, l, 0);
			Sol(r, l, 1);
			if (c[l][r]){
				ans[l] = max(ans[l], max(Sol(l, r, 0), Sol(l, r, 1)) + 1);
				if (ans[l] > mx)
					mx = ans[l],
					bst = l;
			}	
		}
		
	if(k == 0){
		cout << mx << '\n' << bst << '\n';
		return 0;
	}
	
	memset(dp1, -1, sizeof dp1);
	for(int l = 1 ; l <= n ; l ++)
		for(int r = 1 ; r <= n ; r ++)
			Solv(l, r, 0),
			Solv(l, r, 1);
	
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
			if(c[i][j]){
				for (int s = nxt(j); s != i; s = nxt(s))
					for (auto x : g[s])
						if(chk1(x, i, j)){
							ans[i] = max(ans[i], 2 + dp1[j][s][1] + 
											max(dp[j][x][0], dp[i][x][1]));
							if (ans[i] > mx)
								mx = ans[i],
								bst = i;
						}
				
				for (int x = prv(j) ; x != i ; x = prv(x))
					for (auto s : g[x])
						if (chk2(s, i, j)){
							ans[i] = max(ans[i], 2 + dp1[j][x][0] + 
											max(dp[j][s][1], dp[i][s][0]));
							if (ans[i] > mx){
								mx = ans[i];
								bst = i;
							}
						}
			}		
	cout << mx << '\n' << bst << '\n';
	return 0;
}

• Subtask 1: 40 / 100