Submission #364266

# Submission time Handle Problem Language Result Execution time Memory
364266 2021-02-08T16:46:17 Z super_j6 Sailing Race (CEOI12_race) C++14
75 / 100
3000 ms 22764 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, m;
int dp[mxn][mxn][2], dp2[mxn][mxn][2], f[mxn][mxn][2];
vector<int> g[mxn], gr[mxn];
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	for(int i = 0, x; i < n; i++)
	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].push_back(v);
			gr[v].push_back(u);
		} 
	}
	
	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], dpc2 = dp2[i[0]][i[1]][j];
		if(i[0] != i[1]) f[i[0]][i[1]][j] = max(dpc, f[i[0] + j][i[1] - !j][j]);
		for(int k : gr[i[j]]) if(k != i[!j])
		for(int l = 0, ii[2]; l < 2; l++) if((k > i[l]) == l && abs(k - i[!l]) < n){
			ii[l] = k, ii[!l] = i[!l];
			int &dpx = dp[ii[0]][ii[1]][l], &dpx2 = dp2[ii[0]][ii[1]][l];
			dpx = max(dpx, dpc + 1);
			if(j == l && (i[0] == i[1] || dpc2)) dpx2 = max(dpx2, dpc2 + 1);
		}
	}
	
	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], dpc2 = dp2[i[0]][i[1]][j];
		if(dpc > ret) ret = dpc, x = i[j];
		if(m && (i[0] == i[1] || dpc2)){
			for(int p = 0, ii[2]; p < 2; p++)
			for(int k : g[i[!j]]) if(k != i[p] && (k > i[p]) == p && abs(k - i[!p]) < n)
			for(int l : gr[i[j]]) if(l != i[p] && (l > i[p]) == p && abs(l - i[!p]) < n && l != k && (l > k) == j){
				ii[p] = k, ii[!p] = j == p ? i[j] : l;
				int c = f[ii[0] + p][ii[1] - !p][p] + dpc2 + 2;
				if(c > ret) ret = c, x = l;
			}
		}
	}
	
	cout << ret << endl;
	cout << (x % n + 1) << endl;
	
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 4 ms 1408 KB Output is correct
5 Correct 3 ms 1644 KB Output is correct
6 Correct 14 ms 2028 KB Output is correct
7 Correct 10 ms 2412 KB Output is correct
8 Correct 17 ms 2540 KB Output is correct
9 Correct 13 ms 2924 KB Output is correct
10 Correct 37 ms 3564 KB Output is correct
11 Correct 19 ms 3308 KB Output is correct
12 Correct 517 ms 6856 KB Output is correct
13 Correct 721 ms 10988 KB Output is correct
14 Correct 169 ms 16032 KB Output is correct
15 Execution timed out 3078 ms 22124 KB Time limit exceeded
16 Execution timed out 3079 ms 22508 KB Time limit exceeded
17 Execution timed out 3083 ms 22124 KB Time limit exceeded
18 Correct 232 ms 21228 KB Output is correct
19 Execution timed out 3079 ms 22764 KB Time limit exceeded
20 Execution timed out 3078 ms 22764 KB Time limit exceeded