oj.uz

Submission #446602

# Submission time Handle Problem Language Result Execution time Memory
446602 2021-07-22T15:59:37 Z ArianKheirandish Sailing Race (CEOI12_race) C++17
35 / 100
 506 ms 5072 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 ll Inf = 1e9 + 10;
int n, k;
int dp[maxn][maxn][2][2];
vector <int> g[maxn];
bool c[maxn][maxn];

int Sol(int l, int r, int d, int x){
	int &ans = dp[l][r][d][x];
	if(ans != -1)
		return ans;
		
	ans = 0;
	if(l == r)
		return ans;
	
	int v = (!x ? l : r);
	if(!d){
		for(auto i : g[v])
			if(i > l && i < r)
				ans = max(ans, 1 + Sol(l, i, d, 1)),
				ans = max(ans, 1 + Sol(i, r, d, 0));
	}
	else{
		for (auto i : g[v])
			if (i < l)
				ans = max(ans, 1 + Sol(i, l, 0, 0)),
				ans = max(ans, 1 + Sol(i, r, d, 0));
			else if (i > r)
				ans = max(ans, 1 + Sol(l, i, d, 1)),
				ans = max(ans, 1 + Sol(r, i, !d, 1));
	}
	return ans;
}

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;
		}
	}
	
	int ans = 0, bst = 0;
	memset(dp, -1, sizeof dp);
	for(int l = 1 ; l <= n ; l ++)
		for(int r = l + 1 ; r <= n ; r ++){
			int a = Sol(l, r, 0, 0);
			int b = Sol(l, r, 1, 0);
			int C = Sol(l, r, 0, 1);
			int d = Sol(l, r, 1, 1);
			
			if(c[l][r] && 1 + C > ans)
				ans = 1 + C, bst = r;
			if(c[l][r] && 1 + d > ans)
				ans = 1 + d, bst = r;
			if(c[r][l] && 1 + a > ans)
				ans = 1 + a, bst = r;
			if(c[r][l] && 1 + b > ans)
				ans = 1 + b, bst = r;
		}
	cout << ans << '\n' << bst << '\n';
	return 0;
}

Subtask #1
35.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4300 KB Output is correct
2 Incorrect 3 ms 4300 KB Output isn't correct
3 Incorrect 2 ms 4300 KB Output isn't correct
4 Incorrect 3 ms 4428 KB Output isn't correct
5 Correct 3 ms 4428 KB Output is correct
6 Incorrect 3 ms 4428 KB Output isn't correct
7 Correct 6 ms 4428 KB Output is correct
8 Incorrect 4 ms 4428 KB Output isn't correct
9 Incorrect 7 ms 4428 KB Output isn't correct
10 Correct 19 ms 4544 KB Output is correct
11 Correct 10 ms 4428 KB Output is correct
12 Incorrect 32 ms 4564 KB Output isn't correct
13 Incorrect 63 ms 4556 KB Output isn't correct
14 Correct 89 ms 4684 KB Output is correct
15 Incorrect 284 ms 4892 KB Output isn't correct
16 Incorrect 361 ms 5060 KB Output isn't correct
17 Incorrect 280 ms 4900 KB Output isn't correct
18 Correct 142 ms 4744 KB Output is correct
19 Incorrect 439 ms 5072 KB Output isn't correct
20 Incorrect 506 ms 5072 KB Output isn't correct