Submission #364265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
364265	2021-02-08T16:40:49 Z	super_j6	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	24832 KB

race

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#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);
		} 
	}
	
	memset(dp, 0xcf, sizeof(dp));
	memset(dp2, 0xcf, sizeof(dp2));
	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]);
		else dpc = dpc2 = 0;
		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, 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];
		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 && (l > k) == j){
				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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16108 KB	Output is correct
2	Correct	9 ms	16236 KB	Output is correct
3	Correct	10 ms	16236 KB	Output is correct
4	Correct	13 ms	16364 KB	Output is correct
5	Correct	11 ms	16492 KB	Output is correct
6	Correct	25 ms	16620 KB	Output is correct
7	Correct	18 ms	16748 KB	Output is correct
8	Correct	31 ms	16748 KB	Output is correct
9	Correct	21 ms	17004 KB	Output is correct
10	Correct	43 ms	17388 KB	Output is correct
11	Correct	26 ms	17132 KB	Output is correct
12	Correct	607 ms	18540 KB	Output is correct
13	Correct	958 ms	19820 KB	Output is correct
14	Correct	174 ms	21484 KB	Output is correct
15	Execution timed out	3079 ms	24172 KB	Time limit exceeded
16	Execution timed out	3083 ms	24300 KB	Time limit exceeded
17	Execution timed out	3080 ms	23940 KB	Time limit exceeded
18	Correct	230 ms	23532 KB	Output is correct
19	Execution timed out	3054 ms	24684 KB	Time limit exceeded
20	Execution timed out	3048 ms	24832 KB	Time limit exceeded