oj.uz

Submission #702200

# Submission time Handle Problem Language Result Execution time Memory
702200 2023-02-23T10:02:48 Z Josia Sailing Race (CEOI12_race) C++17
0 / 100
 3000 ms 16500 KB 
#include <bits/stdc++.h>

#define int int64_t

using namespace std;

vector<vector<bool>> graphRev;

int n;
bool type;


int DP[500][500][2][2];


void init() {
    for (int i=0; i<500; i++) {
        for (int j = 0; j<500; j++) {
            for (int k = 0; k<2; k++) {
                for (int l = 0; l<2; l++) {
                    DP[i][j][k][l] = -1;
                }
            }
        }
    }
}


int dp(int l, int r, bool pos, bool start) {
    // if (DP[l][r][pos][start] != -1) return DP[l][r][pos][start];
    int res = 0;
    for (int v = (l+1)%n; v!=r; v=(v+1)%n) {
        if (!graphRev[pos?r:l][v]) continue;


        if (start) {
            // if (pos==0) {
                res = max(dp((l+n-1)%n, v, 1, 0)+1, res);
                res = max(dp(v, (r+1)%n, 0, 0)+1, res);
            // }
            // if (pos==1) {
            //     res = max(dp((l+n-1)%n, v, 1, 0)+1, res);
            //     res = max(dp(v, (r+1)%n, 0, 0)+1, res);
            // }
            continue;
        }

        // if (pos==0) {
            res = max(dp(l, v, 1, 0)+1, res);
            res = max(dp(v, r, 0, 0)+1, res);
        // }
        // if (pos==1) {
        //     res = max(dp(l, v, 1, 0)+1, res);
        //     res = max(dp(v, r, 0, 0)+1, res);
        // }
    }
    cerr << l << " " << r << " " << res << "\n";
    return DP[l][r][pos][start] = res;
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    init();

    cin >> n;
    cin >> type;

    graphRev.assign(n,vector<bool>(n, 0));

    for (int i = 0; i<n; i++) {
        int x;
        cin >> x;
        while (x!=0) {
            // graphRev[x-1][i]=1;
            graphRev[i][x-1]=1;
            cin >> x;
        }
    }
    // for (auto i: graphRev) {
    //     for (int j: i) cerr << j << " ";
    //     cerr << "\n";
    // }
    // cerr << "\n";

    if (type == 0) {
        int res = 0;

        for (int i = 0; i<n; i++) {
            res = max(res, dp(i, i, 0, 1));
            cerr << "---------\n";
        }

        cout << res << "\n";
        return 0;
    }

    assert(0);


    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Unexpected end of file - int32 expected
2 Runtime error 10 ms 16244 KB Execution killed with signal 6
3 Runtime error 10 ms 16292 KB Execution killed with signal 6
4 Runtime error 11 ms 16300 KB Execution killed with signal 6
5 Execution timed out 3065 ms 11704 KB Time limit exceeded
6 Runtime error 11 ms 16340 KB Execution killed with signal 6
7 Execution timed out 3067 ms 11744 KB Time limit exceeded
8 Runtime error 10 ms 16340 KB Execution killed with signal 6
9 Execution timed out 3063 ms 11684 KB Time limit exceeded
10 Execution timed out 3054 ms 11760 KB Time limit exceeded
11 Execution timed out 3046 ms 11664 KB Time limit exceeded
12 Runtime error 11 ms 16340 KB Execution killed with signal 6
13 Runtime error 12 ms 16304 KB Execution killed with signal 6
14 Execution timed out 3077 ms 12648 KB Time limit exceeded
15 Runtime error 17 ms 16388 KB Execution killed with signal 6
16 Runtime error 13 ms 16468 KB Execution killed with signal 6
17 Runtime error 13 ms 16468 KB Execution killed with signal 6
18 Execution timed out 3055 ms 12692 KB Time limit exceeded
19 Runtime error 13 ms 16396 KB Execution killed with signal 6
20 Runtime error 17 ms 16500 KB Execution killed with signal 6