| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 101587 | 2019-03-19T04:42:56 Z | choikiwon | Sailing Race (CEOI12_race) | C++17 | 3000 ms | 5800 KB |
#include<bits/stdc++.h>
using namespace std;
const int MN = 555;
int N, T;
int adj[MN][MN];
int dp1[MN][MN][2], dp2[MN][MN][2];
int main() {
scanf("%d %d", &N, &T);
for(int i = 0; i < N; i++) {
while(1) {
int t; scanf("%d", &t);
if(!t) break;
t--;
adj[i][t] = 1;
}
}
for(int d = 1; d < N; d++) {
for(int u = 0; u < N; u++) {
int v = (u + d) % N;
for(int t = 0; t < 2; t++) {
int &ret = dp1[u][v][t];
for(int i = (u + 1) % N; i != v; i = (i + 1) % N) {
if(adj[ (t? u : v) ][i]) {
ret = max(ret, dp1[u][i][0] + 1);
ret = max(ret, dp1[i][v][1] + 1);
}
}
}
}
}
for(int i = 0; i < N; i++) dp2[i][i][0] = dp2[i][i][1] = 0;
for(int d = 1; d < N; d++) {
for(int u = 0; u < N; u++) {
for(int t = 0; t < 2; t++) {
int v = t? (u + d) % N : (u + N - d) % N;
int &ret = dp2[u][v][t] = -1e9;
if(t) {
for(int i = (u + 1) % N;; i = (i + 1) % N) {
if(adj[u][i]) {
ret = max(ret, dp2[i][v][1] + 1);
}
if(i == v) break;
}
}
else {
for(int i = (u + N - 1) % N;; i = (i + N - 1) % N) {
if(adj[u][i]) {
ret = max(ret, dp2[i][v][0] + 1);
}
if(i == v) break;
}
}
}
}
}
int ans = 0;
int p = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) if(i != j && adj[i][j]) {
if(ans < dp1[i][j][0] + 1) {
ans = dp1[i][j][0] + 1;
p = i;
}
if(ans < dp1[j][i][1] + 1) {
ans = dp1[j][i][1] + 1;
p = i;
}
}
}
//*
if(T) {
for(int i = 0; i < N; i++) {
vector<int> mx(N, -1e9);
for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
if(adj[i][j]) {
for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
if(ans < dp2[j][k][1] + 2 + mx[k]) {
ans = dp2[j][k][1] + 2 + mx[k];
p = i;
}
}
}
for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1[i][j][0]);
}
}
}
mx = vector<int>(N, -1e9);
for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
if(adj[i][j]) {
for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
if(ans < dp2[j][k][0] + 2 + mx[k]) {
ans = dp2[j][k][0] + 2 + mx[k];
p = i;
}
}
}
for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1[j][i][1]);
}
}
}
}
for(int i = 0; i < N; i++) {
vector<int> mx(N, -1e9);
for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
if(adj[j][i]) {
for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
if(ans < dp2[i][k][1] + 2 + mx[k]) {
ans = dp2[i][k][1] + 2 + mx[k];
p = j;
}
}
}
for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1[j][i][1]);
}
}
}
mx = vector<int>(N, -1e9);
for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
if(adj[j][i]) {
for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
if(ans < dp2[i][k][0] + 2 + mx[k]) {
ans = dp2[i][k][0] + 2 + mx[k];
p = j;
}
}
}
for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1[i][j][0]);
}
}
}
}
}
//*/
printf("%d\n%d", ans, p + 1);
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 384 KB | Output is correct |
| 2 | Correct | 3 ms | 512 KB | Output is correct |
| 3 | Incorrect | 4 ms | 640 KB | Output isn't correct |
| 4 | Correct | 6 ms | 768 KB | Output is correct |
| 5 | Correct | 7 ms | 896 KB | Output is correct |
| 6 | Correct | 15 ms | 1024 KB | Output is correct |
| 7 | Correct | 13 ms | 1024 KB | Output is correct |
| 8 | Correct | 29 ms | 1280 KB | Output is correct |
| 9 | Correct | 23 ms | 1280 KB | Output is correct |
| 10 | Correct | 24 ms | 1408 KB | Output is correct |
| 11 | Correct | 33 ms | 1408 KB | Output is correct |
| 12 | Correct | 416 ms | 2552 KB | Output is correct |
| 13 | Correct | 1307 ms | 3704 KB | Output is correct |
| 14 | Correct | 1563 ms | 4728 KB | Output is correct |
| 15 | Execution timed out | 3092 ms | 5752 KB | Time limit exceeded |
| 16 | Execution timed out | 3091 ms | 5672 KB | Time limit exceeded |
| 17 | Execution timed out | 3064 ms | 5672 KB | Time limit exceeded |
| 18 | Execution timed out | 3017 ms | 5800 KB | Time limit exceeded |
| 19 | Execution timed out | 3094 ms | 5672 KB | Time limit exceeded |
| 20 | Execution timed out | 3096 ms | 5668 KB | Time limit exceeded |