Submission #168581

# Submission time Handle Problem Language Result Execution time Memory
168581 2019-12-14T00:45:09 Z arnold518 Sailing Race (CEOI12_race) C++14
40 / 100
3000 ms 5880 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;

int N, K;
vector<int> adj[MAXN+10];

int dp[MAXN+10][MAXN+10][5];

int f(int x)
{
	x=(x%N+N)%N;
	if(x==0) x+=N;
	return x;
}

int solve(int l, int r, int s)
{
	int i, j;

	if(l==r) return 0;
	int &ret=dp[l][r][s];
	if(ret!=-1) return ret;
	ret=0;

	if(s==0)
	{
		for(i=f(l+1); i!=f(r+1); i=f(i+1))
		{
			if(!binary_search(adj[l].begin(), adj[l].end(), i)) continue;
			ret=max(ret, solve(f(l+1), i, 1)+1);
			ret=max(ret, solve(i, r, 0)+1);
		}
	}
	else
	{
		for(i=l; i!=r; i=f(i+1))
		{
			if(!binary_search(adj[r].begin(), adj[r].end(), i)) continue;
			ret=max(ret, solve(l, i, 1)+1);
			ret=max(ret, solve(i, f(r-1), 0)+1);
		}	
	}

	//printf("%d %d %d : %d\n", l, r, s, ret);
	return ret;
}

int main()
{
	int i, j;
	scanf("%d%d", &N, &K);
	for(i=1; i<=N; i++)
	{
		int t;
		while(1)
		{
			scanf("%d", &t);
			if(t==0) break;
			adj[i].push_back(t);
		}
		sort(adj[i].begin(), adj[i].end());
	}

	memset(dp, -1, sizeof(dp));

	pii ans={-1, 0};
	for(i=1; i<=N; i++)
	{
		ans=max(ans, {solve(f(i), f(i-1), 0), i});
	}
	printf("%d\n%d", ans.first, ans.second);
}

Compilation message

race.cpp: In function 'int solve(int, int, int)':
race.cpp:24:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp: In function 'int main()':
race.cpp:56:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Incorrect 6 ms 5496 KB Output isn't correct
3 Incorrect 6 ms 5496 KB Output isn't correct
4 Incorrect 7 ms 5496 KB Output isn't correct
5 Correct 10 ms 5364 KB Output is correct
6 Incorrect 12 ms 5368 KB Output isn't correct
7 Correct 20 ms 5496 KB Output is correct
8 Incorrect 16 ms 5496 KB Output isn't correct
9 Correct 31 ms 5372 KB Output is correct
10 Correct 46 ms 5496 KB Output is correct
11 Correct 44 ms 5504 KB Output is correct
12 Incorrect 223 ms 5496 KB Output isn't correct
13 Incorrect 589 ms 5496 KB Output isn't correct
14 Correct 1291 ms 5496 KB Output is correct
15 Execution timed out 3039 ms 5624 KB Time limit exceeded
16 Execution timed out 3063 ms 5880 KB Time limit exceeded
17 Execution timed out 3055 ms 5624 KB Time limit exceeded
18 Correct 2195 ms 5560 KB Output is correct
19 Execution timed out 3037 ms 5880 KB Time limit exceeded
20 Execution timed out 3052 ms 5824 KB Time limit exceeded