Submission #364259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
364259	2021-02-08T16:04:58 Z	super_j6	Sailing Race (CEOI12_race)	C++14	60 / 100	3000 ms	22776 KB

race

#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];
		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) dpx2 = max(dpx2, dp2[i[0]][i[1]][j] + 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];
		if(dpc > ret) ret = dpc, x = i[j];
		if(m){
			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) == j && l != k){
				ii[p] = k, ii[!p] = j == p ? i[j] : l;
				int c = f[ii[0] + p][ii[1] - !p][p] + dp2[i[0]][i[1]][j] + 2;
				if(c > ret) ret = c, x = l;
			}
		}
	}
	
	cout << ret << endl;
	cout << (x % n + 1) << endl;
	
	return 0;
}

Subtask #1

60.0 / 100.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	Incorrect	2 ms	1132 KB	Output isn't correct
4	Incorrect	5 ms	1388 KB	Output isn't correct
5	Correct	4 ms	1644 KB	Output is correct
6	Correct	20 ms	2028 KB	Output is correct
7	Correct	12 ms	2412 KB	Output is correct
8	Correct	23 ms	2540 KB	Output is correct
9	Correct	16 ms	2924 KB	Output is correct
10	Correct	47 ms	3564 KB	Output is correct
11	Correct	23 ms	3308 KB	Output is correct
12	Correct	608 ms	6896 KB	Output is correct
13	Incorrect	991 ms	11040 KB	Output isn't correct
14	Correct	206 ms	15980 KB	Output is correct
15	Execution timed out	3060 ms	22124 KB	Time limit exceeded
16	Execution timed out	3081 ms	22380 KB	Time limit exceeded
17	Execution timed out	3031 ms	21996 KB	Time limit exceeded
18	Correct	274 ms	21408 KB	Output is correct
19	Execution timed out	3077 ms	22768 KB	Time limit exceeded
20	Execution timed out	3078 ms	22776 KB	Time limit exceeded