답안 #446607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446607 2021-07-22T17:01:06 Z ArianKheirandish Sailing Race (CEOI12_race) C++17
40 / 100
3000 ms 4812 KB
//in the name of god//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)		x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair

const int maxn = 500 + 10;
const int LG = 30;
const int Inf = 1e9 + 10;
int n, k;
int dp[maxn][maxn][2], dp1[maxn][maxn][2];
vector <int> g[maxn];
bool c[maxn][maxn];
int ans[maxn];

int nxt(int x){
	return (x == 1) ? n : x - 1;
}

int prv(int x){
	return (x == n) ? 1 : x + 1;
}

int Sol(int l, int r, int x){
	int &anss = dp[l][r][x];
	if(anss != -1)
		return anss;
		
	anss = 0;
	if(x){
		for(int i = nxt(l) ; i != r ; i = nxt(i))
			if(c[r][i])
				anss = max(anss, 1 + Sol(l, i, 1)),
				anss = max(anss, 1 + Sol(r, i, 0));
	}
	else{
		for(int i = prv(l) ; i != r ; i = prv(i))
			if(c[r][i])		
				anss = max(anss, 1 + Sol(l, i, 0)),
				anss = max(anss, 1 + Sol(r, i, 1));		
	}
	return anss;
}

int mx, bst;
int Solv(int l, int r, int x){
	if(l == r)
		return 0;
	
	int &anss = dp[l][r][x];
	if(anss != -1)
		return anss;
	
	anss = -1 * Inf;	
	if(x){
		for (int i = nxt(l) ; 1 ; i = nxt(i)){
			if (c[l][i])
				anss = max(anss, 1 + Solv(i, r, 1));
			if(i == r)
				break;
		}
	}
	else{
		for (int i = nxt(l) ; 1 ; i = nxt(i)){
			if (c[l][i])
				anss = max(anss, 1 + Solv(i, r, 0));
			if(i == r)
				break;
		}
	}
	return anss;
}

bool chk1(int z, int l, int r){
	if(l <= r)
		return !(l <= z && z <= r);
		
	swap(l, r);
	return (l < z && z < r);
}

bool chk2(int z, int l, int r){
	if(l <= r)
		return 	(l < z && z < r);
	swap(l, r);
	return !(l <= z && z <= r);	
}

int main(){_
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++){
		while(true){
			int x;
			cin >> x;
			if(x == 0)
				break;
			g[i].push_back(x);
			c[i][x] = 1;
		}
	}
	
	memset(dp, -1, sizeof(dp));
	for(int l = 1; l <= n; l ++)
		for(int r = 1; r <= n; r ++){
			Sol(r, l, 0);
			Sol(r, l, 1);
			if (c[l][r]){
				ans[l] = max(ans[l], max(Sol(l, r, 0), Sol(l, r, 1)) + 1);
				if (ans[l] > mx)
					mx = ans[l],
					bst = l;
			}	
		}
		
	if(k == 0){
		cout << mx << '\n' << bst << '\n';
		return 0;
	}
	
	memset(dp1, -1, sizeof dp1);
	for(int l = 1 ; l <= n ; l ++)
		for(int r = 1 ; r <= n ; r ++)
			Solv(l, r, 0),
			Solv(l, r, 1);
	
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
			if(c[i][j]){
				for (int s = nxt(j); s != i; s = nxt(s))
					for (auto x : g[s])
						if(chk1(x, i, j)){
							ans[i] = max(ans[i], 2 + dp1[j][s][1] + 
											max(dp[j][x][0], dp[i][x][1]));
							if (ans[i] > mx)
								mx = ans[i],
								bst = i;
						}
				
				for (int x = prv(j) ; x != i ; x = prv(x))
					for (auto s : g[x])
						if (chk2(s, i, j)){
							ans[i] = max(ans[i], 2 + dp1[j][x][0] + 
											max(dp[j][s][1], dp[i][s][0]));
							if (ans[i] > mx){
								mx = ans[i];
								bst = i;
							}
						}
			}		
	cout << mx << '\n' << bst << '\n';
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Incorrect 2 ms 4300 KB Output isn't correct
3 Incorrect 2 ms 4312 KB Output isn't correct
4 Incorrect 3 ms 4300 KB Output isn't correct
5 Correct 3 ms 2296 KB Output is correct
6 Incorrect 7 ms 4428 KB Output isn't correct
7 Correct 6 ms 2380 KB Output is correct
8 Incorrect 8 ms 4428 KB Output isn't correct
9 Correct 11 ms 2444 KB Output is correct
10 Correct 20 ms 2484 KB Output is correct
11 Correct 13 ms 2456 KB Output is correct
12 Incorrect 156 ms 4424 KB Output isn't correct
13 Incorrect 276 ms 4576 KB Output isn't correct
14 Correct 183 ms 2508 KB Output is correct
15 Incorrect 2603 ms 4788 KB Output isn't correct
16 Execution timed out 3091 ms 4780 KB Time limit exceeded
17 Incorrect 2495 ms 4804 KB Output isn't correct
18 Correct 296 ms 2636 KB Output is correct
19 Execution timed out 3090 ms 4804 KB Time limit exceeded
20 Execution timed out 3096 ms 4812 KB Time limit exceeded