oj.uz

답안 #364274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364274 2021-02-08T17:21:03 Z super_j6 Sailing Race (CEOI12_race) C++14
100 / 100
 2031 ms 16072 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];
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
100.0 / 100.0

# 결과 실행 시간 메모리 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 9 ms 1772 KB Output is correct
8 Correct 9 ms 1900 KB Output is correct
9 Correct 12 ms 2156 KB Output is correct
10 Correct 37 ms 2612 KB Output is correct
11 Correct 18 ms 2412 KB Output is correct
12 Correct 120 ms 4716 KB Output is correct
13 Correct 232 ms 7532 KB Output is correct
14 Correct 165 ms 10860 KB Output is correct
15 Correct 1287 ms 15212 KB Output is correct
16 Correct 1755 ms 15596 KB Output is correct
17 Correct 1308 ms 15360 KB Output is correct
18 Correct 253 ms 14444 KB Output is correct
19 Correct 2031 ms 15984 KB Output is correct
20 Correct 2015 ms 16072 KB Output is correct