oj.uz

답안 #364010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364010 2021-02-08T02:39:10 Z super_j6 Sailing Race (CEOI12_race) C++14
5 / 100
 3000 ms 33340 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[0] < 2 * n; i[0]++)
	for(i[1] = i[0]; i[1] < 2 * n && i[1] - i[0] < n; i[1]++)
	for(int j = 0; j < 2; j++)
	for(int k = 0; k < 2; k++){
		pi &dpc = dp[i[0]][i[1]][j][k];
		if(i[0] != i[1]){
			f[i[0]][i[1]][j][k] = max(dpc, f[i[0] + j][i[1] - !j][j][k]);
		}else{
			dpc.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
5.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 5 ms 1132 KB Output isn't correct
5 Incorrect 7 ms 1516 KB Output isn't correct
6 Incorrect 9 ms 1792 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 43 ms 2796 KB Output isn't correct
10 Incorrect 126 ms 3308 KB Output isn't correct
11 Incorrect 83 ms 3212 KB Output isn't correct
12 Incorrect 198 ms 7588 KB Output isn't correct
13 Incorrect 387 ms 14060 KB Output isn't correct
14 Incorrect 716 ms 22324 KB Output isn't correct
15 Runtime error 2777 ms 33340 KB Memory limit exceeded
16 Execution timed out 3065 ms 28364 KB Time limit exceeded
17 Runtime error 2959 ms 33032 KB Memory limit exceeded
18 Incorrect 960 ms 32284 KB Output isn't correct
19 Execution timed out 3091 ms 24812 KB Time limit exceeded
20 Execution timed out 3084 ms 24344 KB Time limit exceeded