oj.uz

Submission #38890

# Submission time Handle Problem Language Result Execution time Memory
38890 2018-01-07T15:04:33 Z aome Sailing Race (CEOI12_race) C++14
15 / 100
 3000 ms 6408 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 505;

int n;
int res, start;
bool subtask;
bool a[N][N];
int f[2][N][N];
int g[2][N][N];

int calF(bool t, int l, int r) {
    int &F = f[t][l][r];
    if (F != -1) return F;
    F = 0;
    if (t == 0) {
        for (int i = l; i != r; i = (i + 1) % n) {
            if (a[l][i]) F = max(F, calF(0, i, r) + 1);
        }
    }
    else {
        for (int i = l; i != r; i = (i + 1) % n) {
            if (a[r][i] && i != l) F = max(F, calF(1, l, i) + 1);
        }
    }
    return F;
}

int calG(bool t, int l, int r) {
    int &G = g[t][l][r];
    if (G != -1) return G;
    G = 0;
    if (t == 0) {
        for (int i = l; i != r; i = (i + 1) % n) {
            if (a[l][i]) G = max(G, max(calG(0, i, r), calG(1, l, i)) + 1);
        }
        if (res < G) {
            res = G, start = l;
        }
    }
    else {
        for (int i = l; i != r; i = (i + 1) % n) {
            if (a[r][i] && i != l) G = max(G, max(calG(1, l, i), calG(0, i, r)) + 1);
        }
        if (res < G) {
            res = G, start = r;
        }
    }
    return G;
}

int main() {
    // subtask 0
    ios::sync_with_stdio(false);
    cin >> n >> subtask;
    for (int i = 0; i < n; ++i) {
        int x;
        while (cin >> x && x) a[i][x - 1] = 1;
    }
    memset(f, -1, sizeof f);
    memset(g, -1, sizeof g);
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                calF(i, j, k), calG(i, j, k);
            }
        }
    }
    cout << res << '\n' << start + 1;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6408 KB Output is correct
2 Incorrect 0 ms 6408 KB Output isn't correct
3 Incorrect 3 ms 6408 KB Output isn't correct
4 Incorrect 0 ms 6408 KB Output isn't correct
5 Correct 3 ms 6408 KB Output is correct
6 Incorrect 9 ms 6408 KB Output isn't correct
7 Incorrect 13 ms 6408 KB Output isn't correct
8 Incorrect 13 ms 6408 KB Output isn't correct
9 Incorrect 26 ms 6408 KB Output isn't correct
10 Incorrect 29 ms 6408 KB Output isn't correct
11 Incorrect 39 ms 6408 KB Output isn't correct
12 Incorrect 243 ms 6408 KB Output isn't correct
13 Incorrect 736 ms 6408 KB Output isn't correct
14 Correct 1739 ms 6408 KB Output is correct
15 Execution timed out 3000 ms 6408 KB Execution timed out
16 Execution timed out 3000 ms 6408 KB Execution timed out
17 Execution timed out 3000 ms 6408 KB Execution timed out
18 Execution timed out 3000 ms 6408 KB Execution timed out
19 Execution timed out 3000 ms 6408 KB Execution timed out
20 Execution timed out 3000 ms 6408 KB Execution timed out