답안 #364264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364264 2021-02-08T16:36:10 Z super_j6 Sailing Race (CEOI12_race) C++14
65 / 100
3000 ms 22796 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];
		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) dpx2 = max(dpx2, dp2[i[0]][i[1]][j] + 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++)
			for(int k : g[i[!j]]) if(k != i[p] && (k > i[p]) == p && abs(k - i[!p]) < n)
			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 2 ms 1132 KB Output is correct
4 Incorrect 5 ms 1388 KB Output isn't correct
5 Correct 4 ms 1792 KB Output is correct
6 Correct 16 ms 2028 KB Output is correct
7 Correct 12 ms 2412 KB Output is correct
8 Correct 25 ms 2540 KB Output is correct
9 Correct 18 ms 2924 KB Output is correct
10 Correct 46 ms 3564 KB Output is correct
11 Correct 23 ms 3308 KB Output is correct
12 Correct 587 ms 6764 KB Output is correct
13 Incorrect 909 ms 11052 KB Output isn't correct
14 Correct 207 ms 16108 KB Output is correct
15 Execution timed out 3071 ms 22124 KB Time limit exceeded
16 Execution timed out 3083 ms 22508 KB Time limit exceeded
17 Execution timed out 3070 ms 21996 KB Time limit exceeded
18 Correct 280 ms 21356 KB Output is correct
19 Execution timed out 3088 ms 22796 KB Time limit exceeded
20 Execution timed out 3100 ms 22764 KB Time limit exceeded