Submission #364271

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
364271	2021-02-08T17:17:01 Z	super_j6	Sailing Race (CEOI12_race)	C++14	90 / 100	1937 ms	16108 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];
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]) dpc = max(dpc, dp[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++){
				int d = 1 - 2 * (j ^ p), k = -1; 
				for(int l : gr[i[j]]){
					if(l != i[p] && (l > i[p]) == p && abs(l - i[!p]) < n && 
					(!~k || d * abs(l - i[!p]) > d * abs(k - i[!p]))){
						k = l;
					}
				} 
				if(~k) for(int l : g[i[!j]]){
					if(l != i[p] && (l > i[p]) == p && 
					abs(l - i[!p]) < n && l != k && (l < k) == j){
						ii[p] = l, ii[!p] = ~d ? i[j] : k;
						int c = dp[ii[0] + p][ii[1] - !p][p] + dpc2 + 2;
						if(c > ret) ret = c, x = k;
					}
				}
			}
		}
	}
	
	cout << ret << endl;
	cout << (x % n + 1) << endl;
	
	return 0;
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	748 KB	Output is correct
3	Correct	1 ms	876 KB	Output is correct
4	Correct	3 ms	1132 KB	Output is correct
5	Correct	3 ms	1260 KB	Output is correct
6	Correct	6 ms	1516 KB	Output is correct
7	Correct	10 ms	1772 KB	Output is correct
8	Incorrect	11 ms	1900 KB	Output isn't correct
9	Correct	13 ms	2156 KB	Output is correct
10	Correct	38 ms	2668 KB	Output is correct
11	Correct	17 ms	2412 KB	Output is correct
12	Correct	112 ms	4716 KB	Output is correct
13	Correct	208 ms	7660 KB	Output is correct
14	Correct	165 ms	10732 KB	Output is correct
15	Incorrect	1252 ms	15424 KB	Output isn't correct
16	Correct	1608 ms	15724 KB	Output is correct
17	Correct	1245 ms	15468 KB	Output is correct
18	Correct	222 ms	14480 KB	Output is correct
19	Correct	1937 ms	16108 KB	Output is correct
20	Correct	1934 ms	16000 KB	Output is correct