답안 #528168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528168 2022-02-19T14:46:57 Z zxcvbnm Sailing Race (CEOI12_race) C++14
10 / 100
19 ms 4936 KB
/*

7 1
5 0 2
5 0
7 0
3 0
4 0
4 3 0
2 1 0

*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int nax = 105;
vector<int> adj[nax];
int dp[nax][nax][nax];
int n, k;

#define watch(x) cerr << (#x) << ": " << x << "\n";

bool in(int l, int r, int x) {
    if (l <= r) {
        return x >= l && x <= r;
    }
    else {
        return x >= l || x <= r;
    }
}

int go(int l, int r, int s) {
//    cout << l+1 << " " << r+1 << " " << s+1 << ":\n";
//    for(int i : path) {
//        cout << i+1 << " ";
//    } cout << "\n";

    if (l == r) {
        return 0;
    }
    if (dp[l][r][s] != -1) {
        return dp[l][r][s];
    }

    int& ret = dp[l][r][s];
    ret = 0;
//    watch(s);

    for(int u : adj[s]) {
//        cout << u << "\n";
        if (!in(l, r, u)) continue;

        int L, R;

        // choice 1
        if (u != l) {
            L = l, R = (((u-1)%n)+n)%n;
            ret = max(ret, go(L, R, u)+1);
        }

        // choice 2
        if (u != r) {
            L = (u+1)%n, R = r;
            ret = max(ret, go(L, R, u)+1);
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    assert(k == 0);
    assert(n <= 105);
    for(int i = 0; i < n; i++) {
        int x;
        while(1) {
            cin >> x;
            if (x == 0) break;
//            cout << i << "->" << x << "\n";
            x--;
            adj[i].push_back(x);
        }
    }

    memset(dp, -1, sizeof dp);
    int mx = -1;
    int idx = 0;
    for(int i = 0; i < n; i++) {
        int curr = go((i+1)%n, (((i-1)%n)+n)%n, i);
        if (curr > mx) {
            mx = curr;
            idx = i;
        }
    }
    cout << mx << "\n";
    cout << idx+1 << "\n";
    return 0;
}

/*

7 0
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0

*/
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4812 KB Output is correct
2 Runtime error 1 ms 452 KB Execution killed with signal 6
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Runtime error 1 ms 448 KB Execution killed with signal 6
5 Incorrect 3 ms 4812 KB Output isn't correct
6 Runtime error 1 ms 460 KB Execution killed with signal 6
7 Incorrect 8 ms 4880 KB Output isn't correct
8 Runtime error 1 ms 460 KB Execution killed with signal 6
9 Correct 8 ms 4804 KB Output is correct
10 Incorrect 19 ms 4936 KB Output isn't correct
11 Incorrect 11 ms 4812 KB Output isn't correct
12 Runtime error 1 ms 460 KB Execution killed with signal 6
13 Runtime error 1 ms 460 KB Execution killed with signal 6
14 Runtime error 1 ms 460 KB Execution killed with signal 6
15 Runtime error 1 ms 456 KB Execution killed with signal 6
16 Runtime error 1 ms 464 KB Execution killed with signal 6
17 Runtime error 1 ms 460 KB Execution killed with signal 6
18 Runtime error 2 ms 520 KB Execution killed with signal 6
19 Runtime error 2 ms 456 KB Execution killed with signal 6
20 Runtime error 1 ms 460 KB Execution killed with signal 6