Submission #78640

#	Time	Username	Problem	Language	Result	Execution time	Memory
78640		ekrem	Sailing Race (CEOI12_race)	C++98	5 / 100	350 ms	2920 KiB

race

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 505
using namespace std;

int n, d, x, dp[N][N], h[N][N];
vector < int > g[N];
pair < int , int > ans;

int f(int bas, int son){
	int &r = dp[bas][son];
	if(r != -1)
		return r;
	r = -inf;
	if(bas == son)
		return r = 0;
	if(h[bas][son])
		r = 1;
	if(bas < son)
		for(int i = bas + 1; i < son; i++)
			r = max(r, f(bas, i) + f(i, son));
	else
		for(int i = son + 1; i < bas; i++)
			r = max(r, f(bas, i) + f(i, son));
	return r;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);

	memset(dp, -1, sizeof dp);

	scanf("%d %d",&n ,&d);
	for(int i = 1; i <= n; i++){
		while(1){
			scanf("%d",&x);
			if(!x)
				break;
			g[i].pb(x);
			h[i][x] = 1;
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < g[i].size(); j++){
			for(int k = 1; k <= n; k++)
				if(k != i)
					ans = max(ans, mp(f(g[i][j], k) + 1, i) );
				// printf("dp[%d][%d] = %d\n", g[i][j], k, f(g[i][j], k));}
		}
	printf("%d\n%d\n", ans.st, ans.nd);
	return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++){
                  ~~^~~~~~~~~~~~~
race.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&d);
  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~

• Subtask 1: 5 / 100