oj.uz

Submission #680364

# Submission time Handle Problem Language Result Execution time Memory
680364 2023-01-10T16:42:37 Z vjudge1 Sailing Race (CEOI12_race) C++17
40 / 100
 142 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 503;

int n, k, dp_before[MAXN][MAXN][2], dp_after[MAXN][MAXN][2];
int ans, ans_node;
vector<int> adj[MAXN];

inline bool include(int i, int j, int k){
	if(i < k) return (i <= j && j <= k);
	return (i <= j || j <= k);
}
inline int nxt(int i){
	return ((i == n - 1) ? 0 : i + 1);
}
inline int prv(int i){
	return ((i == 0) ? n - 1 : i - 1);
}

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(include(i, x, j)){
					dp_after[i][j][0] = max(dp_after[i][j][0], max(dp_after[x][j][0], dp_after[nxt(i)][x][1]) + 1);
				}
			}
			for(int x : adj[j]){
				if(include(i, x, j)){
					dp_after[i][j][1] = max(dp_after[i][j][1], max(dp_after[x][prv(j)][0], dp_after[i][x][1]) + 1);
				}
			}
			if(dp_after[i][j][0] > ans){
				ans = dp_after[i][j][0];
				ans_node = i;
			}
			if(dp_after[i][j][1] > ans){
				ans = dp_after[i][j][1];
				ans_node = j;
			}
		}
	}
	cout << ans << " " << 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 340 KB Output isn't correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 ms 448 KB Output isn't correct
7 Correct 2 ms 596 KB Output is correct
8 Incorrect 2 ms 596 KB Output isn't correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Incorrect 10 ms 1104 KB Output isn't correct
13 Incorrect 21 ms 1492 KB Output isn't correct
14 Correct 33 ms 1876 KB Output is correct
15 Incorrect 98 ms 2520 KB Output isn't correct
16 Incorrect 133 ms 2648 KB Output isn't correct
17 Incorrect 104 ms 2612 KB Output isn't correct
18 Correct 46 ms 2376 KB Output is correct
19 Incorrect 134 ms 2648 KB Output isn't correct
20 Incorrect 142 ms 2644 KB Output isn't correct