oj.uz

답안 #364138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364138 2021-02-08T09:48:28 Z super_j6 Sailing Race (CEOI12_race) C++14
15 / 100
 3000 ms 32388 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;
pi dp[mxn][mxn][2][2], f[mxn][mxn][2][2];
vector<int> g[2][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;
		g[0][u].push_back(v);
		g[1][v].push_back(u);
	}
	
	pi ret;
	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++)
	for(int k = 0; k < 2; k++){
		pi &dpc = dp[i[0]][i[1]][j][k], &fc = f[i[0]][i[1]][j][k];
		if(i[0] != i[1]){
			fc = max(dpc, f[i[0] + j][i[1] - !j][j][k]);
		}else{
			dpc.s = fc.s = i[0];
		}
		
		for(int l : g[k][i[j]])
		for(int p = 0; p < 2; p++){
			if((l > i[p]) == p){
				int ii[2];
				ii[!p] = i[!p], ii[p] = l;
				if(ii[1] - ii[0] < n){
					dp[ii[0]][ii[1]][p][k] = max(dp[ii[0]][ii[1]][p][k], {dpc.f + 1, dpc.s});
					ii[!p] = i[p];
					pi ff[2];
					ff[k] = dpc, ff[!k] = f[ii[0] + p][ii[1] - !p][p][!k];
					ret = max(ret, {ff[0].f + ff[1].f + 1, ff[0].s});
				}
			}
		}
	}
	
	cout << ret.f << " " << (ret.s % n + 1) << endl;
	
	return 0;
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 748 KB Output isn't correct
3 Incorrect 2 ms 1004 KB Output isn't correct
4 Incorrect 3 ms 1132 KB Output isn't correct
5 Incorrect 7 ms 1516 KB Output isn't correct
6 Incorrect 9 ms 1772 KB Output isn't correct
7 Incorrect 31 ms 2156 KB Output isn't correct
8 Incorrect 14 ms 2284 KB Output isn't correct
9 Incorrect 45 ms 2832 KB Output isn't correct
10 Incorrect 126 ms 3308 KB Output isn't correct
11 Correct 66 ms 3180 KB Output is correct
12 Incorrect 221 ms 7788 KB Output isn't correct
13 Incorrect 465 ms 14060 KB Output isn't correct
14 Correct 936 ms 22356 KB Output is correct
15 Execution timed out 3093 ms 27244 KB Time limit exceeded
16 Execution timed out 3073 ms 25004 KB Time limit exceeded
17 Execution timed out 3068 ms 26796 KB Time limit exceeded
18 Incorrect 1452 ms 32388 KB Output isn't correct
19 Execution timed out 3094 ms 23404 KB Time limit exceeded
20 Execution timed out 3095 ms 23944 KB Time limit exceeded