oj.uz

Submission #39378

# Submission time Handle Problem Language Result Execution time Memory
39378 2018-01-13T10:38:43 Z aome Sailing Race (CEOI12_race) C++14
80 / 100
 3000 ms 7156 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
const int INF = 1e9;

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

int nxt(int i) { return i == (n - 1) ? 0 : (i + 1); }
int prv(int i) { return i == 0 ? (n - 1) : (i - 1); }

int calF(int 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 = nxt(i)) {
            if (!a[l][i]) continue;
            F = max(F, max(calF(1, l, i), calF(0, i, r)) + 1);
        }
        if (res < F) res = F, start = l;
    }
    else {
        for (int i = nxt(l); i != r; i = nxt(i)) {
            if (!a[r][i]) continue;
            F = max(F, max(calF(0, i, r), calF(1, l, i)) + 1);
        }
        if (res < F) res = F, start = r;
    }
    return F;
}

int calG(int t, int l, int r) {
    int &G = g[t][l][r];
    if (G != -1) return G;
    if (l == r) return G = 0;
    G = -INF;
    if (t == 0) {
        for (int i = l; i != nxt(r); i = nxt(i)) {
            if (!a[l][i]) continue;
            G = max(G, calG(0, i, r) + 1);
        }
    }
    else {
        for (int i = l; i != r; i = nxt(i)) {
            if (!a[r][i]) continue;
            G = max(G, calG(1, l, i) + 1);
        }
    }
    return G;   
}

void updRes(int x, int y) {
    if (res < x) res = x, start = y;
}

int main() {
    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);
            }
        }
    }
    if (subtask == 0) {
        cout << res << '\n' << start + 1; return 0;
    }
    // fix S
    for (int S = 0; S < n; ++S) {
        memset(best, 0, sizeof best);
        for (int T = nxt(S); T != S; T = nxt(T)) {
            if (a[S][T]) {
                for (int i = T; i != S; i = nxt(i)) {
                    updRes(calG(0, T, i) + best[i] + 1, S);
                }
            }
            for (int i = T; i != S; i = nxt(i)) {
                if (!a[i][T]) continue;
                best[i] = max(best[i], calF(1, S, T) + 1);
            }
        }
    }
    for (int S = 0; S < n; ++S) {
        memset(best, 0, sizeof best);
        for (int T = prv(S); T != S; T = prv(T)) {
            if (a[S][T]) {
                for (int i = T; i != S; i = prv(i)) {
                    updRes(calG(1, i, T) + best[i] + 1, S);
                }
            }
            for (int i = T; i != S; i = prv(i)) {
                if (!a[i][T]) continue;
                best[i] = max(best[i], calF(0, T, S) + 1);
            }   
        }
    }
    // fix T
    for (int T = 0; T < n; ++T) {
        memset(best, 0, sizeof best);
        for (int S = nxt(T); S != T; S = nxt(S)) {
            if (a[S][T]) {
                for (int i = S; i != T; i = nxt(i)) {
                    updRes(calG(1, i, T) + best[i] + 1, S);
                }
            }
            for (int i = S; i != T; i = nxt(i)) {
                if (!a[i][S]) continue;
                best[i] = max(best[i], calF(1, T, S) + 1);
            }
        }
    }
    for (int T = 0; T < n; ++T) {
        memset(best, 0, sizeof best);
        for (int S = prv(T); S != T; S = prv(S)) {
            if (a[S][T]) {
                for (int i = S; i != T; i = prv(i)) {
                    updRes(calG(0, T, i) + best[i] + 1, S);
                }
            }
            for (int i = S; i != T; i = prv(i)) {
                if (!a[i][S]) continue;
                best[i] = max(best[i], calF(0, S, T) + 1);
            }
        }
    }
    cout << res << '\n' << start + 1;
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7156 KB Output is correct
2 Correct 0 ms 7156 KB Output is correct
3 Incorrect 0 ms 7156 KB Output isn't correct
4 Correct 3 ms 7156 KB Output is correct
5 Correct 0 ms 7156 KB Output is correct
6 Correct 6 ms 7156 KB Output is correct
7 Correct 9 ms 7156 KB Output is correct
8 Correct 13 ms 7156 KB Output is correct
9 Correct 23 ms 7156 KB Output is correct
10 Correct 19 ms 7156 KB Output is correct
11 Correct 23 ms 7156 KB Output is correct
12 Correct 216 ms 7156 KB Output is correct
13 Correct 523 ms 7156 KB Output is correct
14 Correct 469 ms 7156 KB Output is correct
15 Correct 2779 ms 7156 KB Output is correct
16 Execution timed out 3000 ms 7156 KB Execution timed out
17 Correct 2736 ms 7156 KB Output is correct
18 Correct 799 ms 7156 KB Output is correct
19 Execution timed out 3000 ms 7156 KB Execution timed out
20 Execution timed out 3000 ms 7156 KB Execution timed out