Submission #132247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132247	2019-07-18T14:54:16 Z	amoo_safar	Sailing Race (CEOI12_race)	C++14	40 / 100	1597 ms	2636 KB

race

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int Maxn = 5e2 + 10;

bool G[Maxn][Maxn];

int n, dp[Maxn][Maxn][2];

int nxt(int y){
	return (y + 1) % n;
}
int prev(int y){
	return (y - 1 + n) % n;
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k;
	cin >> n >> k;
	if(k == 1){
		cout << G[5000][5000];
		return 0;
	}
	int adj;
	for(int i = 0; i < n; i++){
		while(true){
			cin >> adj;
			adj --;
			if(adj == -1) break;
			G[i][adj] = true;
		}
	}
	
	for(int l = 1; l <= n; l++){
		for(int i = 0; i < n; i++){
			int j = (i + l) % n;
			dp[i][j][0] = 0;
			for(int k = nxt(i); k != j; k = nxt(k)){
				if(G[i][k]) dp[i][j][0] = max( dp[i][j][0], max(dp[k][j][0], dp[k][i][1]) + 1);
			}
			j = (i - l + n) % n;
			dp[i][j][1] = 0;
			for(int k = prev(i); k != j; k = prev(k)){
				if(G[i][k]) dp[i][j][1] = max( dp[i][j][1], max(dp[k][j][1], dp[k][i][0]) + 1);
			}
		}
	}
	int ans = 0, st = 0;
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i][i][0]);
		if(ans == dp[i][i][0]) st = i;
	}
	cout << ans << '\n' << st + 1 << '\n';
	
	return 0;
}
/*
7 0
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

Compilation message

race.cpp: In function 'int main()':
race.cpp:27:23: warning: array subscript is above array bounds [-Warray-bounds]
   cout << G[5000][5000];
           ~~~~~~~~~~~~^
race.cpp:27:17: warning: array subscript is above array bounds [-Warray-bounds]
   cout << G[5000][5000];
           ~~~~~~^

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	3 ms	508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	2 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Correct	5 ms	632 KB	Output is correct
6	Runtime error	3 ms	476 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Correct	9 ms	632 KB	Output is correct
8	Runtime error	3 ms	404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	15 ms	760 KB	Output is correct
10	Correct	16 ms	760 KB	Output is correct
11	Correct	20 ms	892 KB	Output is correct
12	Runtime error	2 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Correct	826 ms	2180 KB	Output is correct
15	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Correct	1597 ms	2636 KB	Output is correct
19	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)