Submission #364011

# Submission time Handle Problem Language Result Execution time Memory
364011 2021-02-08T02:47:04 Z super_j6 Sailing Race (CEOI12_race) C++14
5 / 100
3000 ms 33192 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], &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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 748 KB Output isn't correct
3 Incorrect 1 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 10 ms 1772 KB Output isn't correct
7 Incorrect 32 ms 2156 KB Output isn't correct
8 Incorrect 17 ms 2284 KB Output isn't correct
9 Incorrect 43 ms 2944 KB Output isn't correct
10 Incorrect 129 ms 3424 KB Output isn't correct
11 Incorrect 66 ms 3200 KB Output isn't correct
12 Incorrect 196 ms 7628 KB Output isn't correct
13 Incorrect 399 ms 14060 KB Output isn't correct
14 Incorrect 730 ms 22380 KB Output isn't correct
15 Execution timed out 3014 ms 33192 KB Time limit exceeded
16 Execution timed out 3078 ms 27616 KB Time limit exceeded
17 Runtime error 2878 ms 33024 KB Memory limit exceeded
18 Incorrect 1002 ms 32364 KB Output isn't correct
19 Execution timed out 3078 ms 24816 KB Time limit exceeded
20 Execution timed out 3039 ms 24224 KB Time limit exceeded