oj.uz

답안 #364272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364272 2021-02-08T17:18:16 Z super_j6 Sailing Race (CEOI12_race) C++14
100 / 100
 2089 ms 15988 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 2 ms 876 KB Output is correct
4 Correct 5 ms 1132 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 8 ms 1516 KB Output is correct
7 Correct 12 ms 1772 KB Output is correct
8 Correct 11 ms 1900 KB Output is correct
9 Correct 12 ms 2156 KB Output is correct
10 Correct 35 ms 2668 KB Output is correct
11 Correct 17 ms 2412 KB Output is correct
12 Correct 121 ms 4844 KB Output is correct
13 Correct 222 ms 7664 KB Output is correct
14 Correct 158 ms 10988 KB Output is correct
15 Correct 1377 ms 15276 KB Output is correct
16 Correct 1614 ms 15696 KB Output is correct
17 Correct 1284 ms 15340 KB Output is correct
18 Correct 225 ms 14488 KB Output is correct
19 Correct 2044 ms 15928 KB Output is correct
20 Correct 2089 ms 15988 KB Output is correct