제출 #59292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59292		IvanC	Sailing Race (CEOI12_race)	C++17	40 / 100	208 ms	9428 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

vector<int> grafo[MAXN];
int dp[MAXN][MAXN],N,K;


int solve(int i,int j){
	if(dp[i][j] != -1) return dp[i][j];
	if(i == j) return dp[i][j] = 0;
	int best = 0;
	
	if(i < j){
		for(int k : grafo[i]){
			if(k >= min(i,j) && k <= max(i,j)){
				int candidate = max(solve(k,j),solve(k,i+1)) + 1;
				best = max(best,candidate);
			}
		}
	}
	else{
		for(int k : grafo[i]){
			if(k >= min(i,j) && k <= max(i,j)){
				int candidate = max(solve(k,i-1),solve(k,j)) + 1;
				best = max(best,candidate);
			}
		}
	}
	
	return dp[i][j] = best;	
	
}

void adiciona(int i,int j){
	grafo[i].push_back(j);
	grafo[i].push_back(j+N);
	grafo[i+N].push_back(j);
	grafo[i+N].push_back(j+N);
}

int main(){
	
	memset(dp,-1,sizeof(dp));
	cin >> N >> K;
	assert(K != 1);
	
	for(int i = 1;i<=N;i++){
		int x;
		while(cin >> x && x){
			adiciona(i,x);
		}
	}
	
	int best = -1,ans = 0;
	for(int i = 1,j = N;i<=N;i++,j++){
		int candidate = solve(i,j);
		if(candidate > best){
			best = candidate;
			ans = i;
		}
	}
	
	cout << best << endl << ans << endl;
	
	return 0;
	
}

• Subtask 1: 40 / 100