oj.uz

Submission #39375

# Submission time Handle Problem Language Result Execution time Memory
39375 2018-01-13T09:48:02 Z aome Sailing Race (CEOI12_race) C++14
0 / 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 bestVal[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 != 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) {
        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) + bestVal[i] + 1, S);
                }
            }
            for (int i = T; i != S; i = nxt(i)) {
                if (!a[i][T]) continue;
                bestVal[i] = max(bestVal[i], calF(1, S, T) + 1);
            }
        }
    }
    memset(bestVal, 0, sizeof bestVal);
    for (int S = 0; S < n; ++S) {
        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) + bestVal[i] + 1, S);
                }
            }
            for (int i = T; i != S; i = prv(i)) {
                if (!a[i][T]) continue;
                bestVal[i] = max(bestVal[i], calF(0, T, S) + 1);
            }   
        }
    }
    // fix T
    memset(bestVal, 0, sizeof bestVal);
    for (int T = 0; T < n; ++T) {
        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) + bestVal[i] + 1, S);
                }
            }
            for (int i = S; i != T; i = nxt(i)) {
                if (!a[i][S]) continue;
                bestVal[i] = max(bestVal[i], calF(1, T, S) + 1);
            }
        }
    }
    memset(bestVal, 0, sizeof bestVal);
    for (int T = 0; T < n; ++T) {
        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) + bestVal[i] + 1, S);
                }
            }
            for (int i = S; i != T; i = prv(i)) {
                if (!a[i][S]) continue;
                bestVal[i] = max(bestVal[i], calF(0, S, T) + 1);
            }
        }
    }
    cout << res << '\n' << start + 1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 7156 KB Output isn't correct
2 Incorrect 0 ms 7156 KB Output isn't correct
3 Incorrect 0 ms 7156 KB Output isn't correct
4 Incorrect 3 ms 7156 KB Output isn't correct
5 Incorrect 0 ms 7156 KB Output isn't correct
6 Incorrect 6 ms 7156 KB Output isn't correct
7 Incorrect 9 ms 7156 KB Output isn't correct
8 Incorrect 9 ms 7156 KB Output isn't correct
9 Incorrect 16 ms 7156 KB Output isn't correct
10 Incorrect 16 ms 7156 KB Output isn't correct
11 Incorrect 19 ms 7156 KB Output isn't correct
12 Incorrect 196 ms 7156 KB Output isn't correct
13 Incorrect 486 ms 7156 KB Output isn't correct
14 Incorrect 473 ms 7156 KB Output isn't correct
15 Incorrect 2749 ms 7156 KB Output isn't correct
16 Execution timed out 3000 ms 7156 KB Execution timed out
17 Incorrect 2619 ms 7156 KB Output isn't correct
18 Incorrect 716 ms 7156 KB Output isn't correct
19 Execution timed out 3000 ms 7156 KB Execution timed out
20 Execution timed out 3000 ms 7156 KB Execution timed out