답안 #132259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132259	2019-07-18T15:22:14 Z	amoo_safar	Sailing Race (CEOI12_race)	C++14	45 / 100	3000 ms	2696 KB

race

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int Maxn = 5e2 + 10;
const int Inf = 10000;
bool G[Maxn][Maxn];

int n, dp[Maxn][Maxn][2], dp2[Maxn], dp3[Maxn];

int nxt(int y){
	return (y + 1) % n;
}
int prev(int y){
	return (y - 1 + n) % n;
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k;
	cin >> n >> k;
	
	int adj;
	for(int i = 0; i < n; i++){
		while(true){
			cin >> adj;
			adj --;
			if(adj == -1) break;
			G[i][adj] = true;
		}
	}
	
	for(int l = 1; l <= n; l++){
		for(int i = 0; i < n; i++){
			int j = (i + l) % n;
			dp[i][j][0] = 0;
			for(int k = nxt(i); k != j; k = nxt(k)){
				if(G[i][k]) dp[i][j][0] = max( dp[i][j][0], max(dp[k][j][0], dp[k][i][1]) + 1);
			}
			j = (i - l + n) % n;
			dp[i][j][1] = 0;
			for(int k = prev(i); k != j; k = prev(k)){
				if(G[i][k]) dp[i][j][1] = max( dp[i][j][1], max(dp[k][j][1], dp[k][i][0]) + 1);
			}
		}
	}
	int ans = 0, st = 0, res;
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i][i][0]);
		if(ans == dp[i][i][0]) st = i;
	}
	
	if(k == 1){
		for(int sec = 0; sec < n; sec ++){
			fill(dp2, dp2 + Maxn, -Inf);
			dp2[sec] = 0;
			for(int fir = nxt(sec); fir != sec; fir = nxt(fir)){
				for(int bef = sec; bef != fir; bef = nxt(bef)){
					if(G[bef][fir]) dp2[fir] = max(dp2[fir], dp2[bef] + 1);
				}
			}
			fill(dp3, dp3 + Maxn, -Inf);
			for(int fir = nxt(sec); fir != sec; fir = nxt(fir)){
				
				if(fir != nxt(sec)){
					res = 0;
					for(int P = nxt(fir); P != sec; P = nxt(P)){
						res = max(res, 1 + dp3[P] + max(dp[P][sec][0], dp[P][fir][1]) );
					}
					if(res > ans){
						ans = res;
						st = fir;
					}
				}
				for(int i = 0; i < n; i++) if(G[fir][i]) dp3[i] = max(dp3[i], dp2[fir] + 1);
			}
		}
	}
	
	cout << ans << '\n' << st + 1 << '\n';
	
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Incorrect	3 ms	504 KB	Output isn't correct
4	Incorrect	4 ms	504 KB	Output isn't correct
5	Correct	4 ms	632 KB	Output is correct
6	Incorrect	9 ms	632 KB	Output isn't correct
7	Correct	8 ms	632 KB	Output is correct
8	Incorrect	17 ms	632 KB	Output isn't correct
9	Correct	14 ms	760 KB	Output is correct
10	Correct	16 ms	760 KB	Output is correct
11	Correct	20 ms	888 KB	Output is correct
12	Incorrect	246 ms	1296 KB	Output isn't correct
13	Incorrect	733 ms	1748 KB	Output isn't correct
14	Correct	820 ms	2168 KB	Output is correct
15	Execution timed out	3023 ms	2696 KB	Time limit exceeded
16	Execution timed out	3076 ms	2680 KB	Time limit exceeded
17	Execution timed out	3033 ms	2680 KB	Time limit exceeded
18	Correct	1688 ms	2648 KB	Output is correct
19	Execution timed out	3035 ms	2680 KB	Time limit exceeded
20	Execution timed out	3042 ms	2680 KB	Time limit exceeded