답안 #364268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364268 2021-02-08T17:08:17 Z super_j6 Sailing Race (CEOI12_race) C++14
80 / 100
1991 ms 22960 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 k = i[!p]; 
				for(int l : g[i[!j]]){
					if(l != i[p] && (l > i[p]) == p && abs(l - i[!p]) < n && 
					abs(l - i[!p]) > abs(k - i[!p])){
						k = l;
					}
				} 
				if(k != i[!p]) 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] + 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 10 ms 2412 KB Output is correct
8 Incorrect 9 ms 2540 KB Output isn't correct
9 Correct 16 ms 2924 KB Output is correct
10 Correct 37 ms 3584 KB Output is correct
11 Correct 19 ms 3328 KB Output is correct
12 Correct 137 ms 6764 KB Output is correct
13 Correct 213 ms 11136 KB Output is correct
14 Correct 170 ms 15872 KB Output is correct
15 Correct 1275 ms 22076 KB Output is correct
16 Incorrect 1551 ms 22508 KB Output isn't correct
17 Incorrect 1267 ms 22216 KB Output isn't correct
18 Correct 238 ms 21228 KB Output is correct
19 Correct 1944 ms 22960 KB Output is correct
20 Correct 1991 ms 22912 KB Output is correct