oj.uz

Submission #364137

# Submission time Handle Problem Language Result Execution time Memory
364137 2021-02-08T09:47:44 Z super_j6 Sailing Race (CEOI12_race) C++14
15 / 100
 377 ms 11976 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int mxn = 1000;
int n, k;
int g[mxn][mxn];
int dp[mxn][mxn][2];
vector<int> gr[mxn];
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	
	for(int i = 0, x; i < n; i++){
		for(int j = 0; j < 2; j++) g[j * n + i][j * n + i] = 1;
		for(cin >> x; x; cin >> x)
		for(int j = 0; j < 2; j++)
		for(int l = 0; l < 2; l++){
			int u = j * n + i, v = l * n + x - 1;
			if(abs(u - v) < n){
				g[u][v] = 1;
				gr[u].push_back(v);
			}
		}
	}
	
	int ret = 0, x = 0;
	for(int i[2] = {0}; i[1] < 2 * n; i[1]++)
	for(i[0] = i[1]; ~i[0] && i[1] - i[0] < n; i[0]--)
	for(int j = 0; j < 2; j++){
		int &dpc = dp[i[0]][i[1]][j];
		for(int p = 0; p < 2; p++) if(g[i[j]][i[p]])
		for(int l : gr[i[p]]) if(l >= i[0] && l <= i[1] && l != i[j]){
			int ii[2];
			ii[j] = l, ii[!j] = i[!j];
			dpc = max(dpc, dp[ii[0]][ii[1]][p] + 1);
		}
		if(dpc > ret) ret = dpc, x = i[j];
	}
	
	cout << ret << " " << (x % n + 1) << endl;
	
	return 0;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Incorrect 1 ms 1004 KB Output isn't correct
5 Incorrect 2 ms 1260 KB Output isn't correct
6 Incorrect 2 ms 1388 KB Output isn't correct
7 Correct 6 ms 1644 KB Output is correct
8 Incorrect 3 ms 1772 KB Output isn't correct
9 Incorrect 7 ms 1900 KB Output isn't correct
10 Correct 23 ms 2284 KB Output is correct
11 Incorrect 10 ms 2156 KB Output isn't correct
12 Incorrect 24 ms 4096 KB Output isn't correct
13 Incorrect 54 ms 6252 KB Output isn't correct
14 Incorrect 80 ms 8684 KB Output isn't correct
15 Incorrect 232 ms 11692 KB Output isn't correct
16 Incorrect 293 ms 11756 KB Output isn't correct
17 Incorrect 238 ms 11556 KB Output isn't correct
18 Incorrect 106 ms 11428 KB Output isn't correct
19 Incorrect 356 ms 11884 KB Output isn't correct
20 Incorrect 377 ms 11976 KB Output isn't correct