Submission #78641

# Submission time Handle Problem Language Result Execution time Memory
78641 2018-10-06T18:28:18 Z ekrem Sailing Race (CEOI12_race) C++
5 / 100
516 ms 2996 KB
#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 = max(r, -inf);
}

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

race.cpp: In function 'int main()':
race.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++){
                  ~~^~~~~~~~~~~~~
race.cpp:37: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:40:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Incorrect 3 ms 1404 KB Output isn't correct
3 Incorrect 3 ms 1480 KB Output isn't correct
4 Incorrect 3 ms 1496 KB Output isn't correct
5 Incorrect 4 ms 1544 KB Output isn't correct
6 Incorrect 5 ms 1556 KB Output isn't correct
7 Incorrect 5 ms 1812 KB Output isn't correct
8 Incorrect 5 ms 1812 KB Output isn't correct
9 Incorrect 7 ms 1812 KB Output isn't correct
10 Incorrect 13 ms 1812 KB Output isn't correct
11 Incorrect 9 ms 1812 KB Output isn't correct
12 Incorrect 35 ms 2100 KB Output isn't correct
13 Incorrect 98 ms 2228 KB Output isn't correct
14 Incorrect 213 ms 2440 KB Output isn't correct
15 Incorrect 460 ms 2808 KB Output isn't correct
16 Incorrect 478 ms 2868 KB Output isn't correct
17 Incorrect 516 ms 2868 KB Output isn't correct
18 Incorrect 397 ms 2868 KB Output isn't correct
19 Incorrect 509 ms 2996 KB Output isn't correct
20 Incorrect 500 ms 2996 KB Output isn't correct