답안 #364269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364269 2021-02-08T17:10:04 Z super_j6 Sailing Race (CEOI12_race) C++14
75 / 100
1780 ms 22900 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 Correct 1 ms 1132 KB Output is correct
4 Incorrect 3 ms 1388 KB Output isn't correct
5 Correct 3 ms 1644 KB Output is correct
6 Correct 7 ms 2028 KB Output is correct
7 Correct 11 ms 2412 KB Output is correct
8 Incorrect 11 ms 2540 KB Output isn't correct
9 Correct 16 ms 3052 KB Output is correct
10 Correct 41 ms 3564 KB Output is correct
11 Correct 25 ms 3308 KB Output is correct
12 Correct 107 ms 6784 KB Output is correct
13 Correct 197 ms 11000 KB Output is correct
14 Correct 205 ms 15852 KB Output is correct
15 Incorrect 1183 ms 22068 KB Output isn't correct
16 Incorrect 1472 ms 22380 KB Output isn't correct
17 Incorrect 1255 ms 22092 KB Output isn't correct
18 Correct 254 ms 21228 KB Output is correct
19 Correct 1780 ms 22892 KB Output is correct
20 Correct 1764 ms 22900 KB Output is correct