답안 #364267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364267 2021-02-08T17:03:03 Z super_j6 Sailing Race (CEOI12_race) C++14
55 / 100
1942 ms 23008 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++){
				int d = 1 - 2 * (j ^ p), k = -1; 
				for(int l : g[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 : 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] = ~d ? 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Incorrect 4 ms 1388 KB Output isn't correct
5 Correct 3 ms 1644 KB Output is correct
6 Incorrect 7 ms 2028 KB Output isn't correct
7 Correct 10 ms 2412 KB Output is correct
8 Incorrect 9 ms 2540 KB Output isn't correct
9 Correct 16 ms 2944 KB Output is correct
10 Correct 37 ms 3692 KB Output is correct
11 Correct 19 ms 3308 KB Output is correct
12 Incorrect 128 ms 6764 KB Output isn't correct
13 Incorrect 209 ms 10988 KB Output isn't correct
14 Correct 173 ms 15852 KB Output is correct
15 Correct 1257 ms 22048 KB Output is correct
16 Incorrect 1580 ms 22652 KB Output isn't correct
17 Incorrect 1227 ms 21996 KB Output isn't correct
18 Correct 237 ms 21228 KB Output is correct
19 Incorrect 1928 ms 23008 KB Output isn't correct
20 Correct 1942 ms 22764 KB Output is correct