답안 #552055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552055 2022-04-22T10:47:12 Z Alexandruabcde Sailing Race (CEOI12_race) C++14
40 / 100
158 ms 2652 KB
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 502;

int N, K;

vector <int> G[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;

    for (int i = 1; i <= N; ++ i ) {
        int x;
        cin >> x;

        while (x != 0) {
            G[i].push_back(x);
            cin >> x;
        }
    }
}

bool Between (int val, int st, int dr) {
    if (st <= dr)
        return (st <= val && val <= dr);

    return (st <= val || val <= dr);
}

int Before (int val) {
    if (val > 1) return val-1;

    return N;
}

int After (int val) {
    if (val < N) return val + 1;

    return 1;
}

int dp[NMAX][NMAX][2];

void Precompute () {
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j )
            for (int c = 0; c < 2; ++ c )
                dp[i][j][c] = 0;

    for (int lg = 2; lg <= N; ++ lg ) {
        for (int i = 1; i <= N; ++ i ) {
            int j = i + lg - 1;
            if (j > N) j -= N;

            dp[i][j][0] = dp[i][j][1] = 0;

            ///Caz I: din i
            for (auto vec : G[i]) {
                if (!Between(vec, i, j)) continue;

                dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[After(i)][vec][1], dp[vec][j][0]));
            }

            ///Caz II: din j
            for (auto vec : G[j]) {
                if (!Between(vec, i, j)) continue;

                dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[i][vec][1], dp[vec][Before(j)][0]));
            }
        }
    }
}

void Solve_Case_0 () {
    int ans = 0, start = 1;
    for (int i = 1; i <= N; ++ i ) {
        for (auto vec : G[i]) {
            ///i -> vec

            int posib = 1 + max(dp[After(i)][vec][1], dp[vec][Before(i)][0]);

            if (posib > ans) {
                ans = posib;
                start = i;
            }
        }
    }

    cout << ans << '\n' << start << '\n';
}

int main () {
    Read();
    Precompute();
    if (K == 0) Solve_Case_0 ();

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 472 KB Unexpected end of file - int32 expected
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 ms 468 KB Unexpected end of file - int32 expected
7 Correct 2 ms 604 KB Output is correct
8 Incorrect 2 ms 596 KB Unexpected end of file - int32 expected
9 Correct 4 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 5 ms 740 KB Output is correct
12 Incorrect 11 ms 1108 KB Unexpected end of file - int32 expected
13 Incorrect 20 ms 1492 KB Unexpected end of file - int32 expected
14 Correct 39 ms 2004 KB Output is correct
15 Incorrect 110 ms 2516 KB Unexpected end of file - int32 expected
16 Incorrect 140 ms 2652 KB Unexpected end of file - int32 expected
17 Incorrect 118 ms 2516 KB Unexpected end of file - int32 expected
18 Correct 48 ms 2388 KB Output is correct
19 Incorrect 157 ms 2644 KB Unexpected end of file - int32 expected
20 Incorrect 158 ms 2644 KB Unexpected end of file - int32 expected