oj.uz

답안 #168583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168583 2019-12-14T00:50:16 Z arnold518 Sailing Race (CEOI12_race) C++14
40 / 100
 3000 ms 6392 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
int adj[MAXN+10][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(!adj[l][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(!adj[r][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][t]=1;
		}
	}

	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:27:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp: In function 'int main()':
race.cpp:59:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp:60: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:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 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 8 ms 5496 KB Output isn't correct
5 Correct 10 ms 5496 KB Output is correct
6 Incorrect 11 ms 5496 KB Output isn't correct
7 Correct 17 ms 5496 KB Output is correct
8 Incorrect 16 ms 5624 KB Output isn't correct
9 Correct 28 ms 5624 KB Output is correct
10 Correct 36 ms 5628 KB Output is correct
11 Correct 37 ms 5624 KB Output is correct
12 Incorrect 210 ms 5880 KB Output isn't correct
13 Incorrect 563 ms 6052 KB Output isn't correct
14 Correct 1239 ms 6264 KB Output is correct
15 Execution timed out 3016 ms 6392 KB Time limit exceeded
16 Execution timed out 3033 ms 6392 KB Time limit exceeded
17 Execution timed out 3034 ms 6392 KB Time limit exceeded
18 Correct 2170 ms 6392 KB Output is correct
19 Execution timed out 3051 ms 6392 KB Time limit exceeded
20 Execution timed out 3052 ms 6392 KB Time limit exceeded