oj.uz

Submission #679072

# Submission time Handle Problem Language Result Execution time Memory
679072 2023-01-07T11:36:16 Z vjudge1 Sailing Race (CEOI12_race) C++17
40 / 100
 225 ms 6668 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;


int n, k, dp[MAXN][MAXN][2][2], ans, ans_node;
vector<int> adj[MAXN];
bool bio[MAXN];
int cur_i, cur_j, cur_b;
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
		int x; cin >> x;
		while(x){
			--x;
			adj[i].push_back(x);
			cin >> x;
		}
	}
	for(int off = 1; off < n; ++off){
		for(int i = 0; i < n; ++i){
			int j = (i + off) % n;
			for(int x : adj[i]){
				if((i < j && i < x && x <= j) || (i > j && (i < x || x <= j))){
					dp[i][j][0][0] = max(dp[i][j][0][0], max(dp[(i + 1) % n][x][1][1], dp[x][j][0][0]) + 1);
					dp[i][j][0][1] = max(dp[i][j][0][1], max(dp[(i + 1) % n][x][1][1], dp[x][j][0][1]) + 1);
				}
			}
			for(int x : adj[j]){
				if((i < j && i <= x && x < j) || (i > j && (i <= x || x < j))){
					dp[i][j][1][0] = max(dp[i][j][1][0], max(dp[i][x][1][0], dp[x][(j - 1 + n) % n][0][1]) + 1);
					dp[i][j][1][1] = max(dp[i][j][1][1], max(dp[i][x][1][1], dp[x][(j - 1 + n) % n][0][1]) + 1);
				}
			}
			ans = max(ans, dp[i][j][0][0]);
			ans = max(ans, dp[i][j][1][0]);
			if(dp[i][j][0][0] == ans){
				ans_node = i;
			}
			if(dp[i][j][1][0] == ans){
				ans_node = j;
			}
		}
	}
	cout << ans << "\n" << ans_node + 1;
	return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Correct 1 ms 460 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Correct 3 ms 596 KB Output is correct
8 Incorrect 2 ms 716 KB Output isn't correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 9 ms 852 KB Output is correct
11 Correct 6 ms 916 KB Output is correct
12 Incorrect 18 ms 1776 KB Output isn't correct
13 Incorrect 28 ms 2952 KB Output isn't correct
14 Correct 49 ms 4476 KB Output is correct
15 Incorrect 157 ms 6520 KB Output isn't correct
16 Incorrect 191 ms 6592 KB Output isn't correct
17 Incorrect 152 ms 6436 KB Output isn't correct
18 Correct 65 ms 6220 KB Output is correct
19 Incorrect 225 ms 6668 KB Output isn't correct
20 Incorrect 217 ms 6636 KB Output isn't correct