Submission #59283

#	Time	Username	Problem	Language	Result	Execution time	Memory
59283		IvanC	Sailing Race (CEOI12_race)	C++17	10 / 100	48 ms	9532 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;
	
	for(int k : grafo[i]){
		if(k > i && k <= j){
			best = max(best, solve(k,j) + 1 );
		}
	}
	
	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: 10 / 100