Submission #328797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328797	2020-11-18T06:00:42 Z	thecodingwizard	Sailing Race (CEOI12_race)	C++11	40 / 100	918 ms	4844 KB

race

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 500
int n, k; 
vector<int> adj[maxn];

int memo[maxn][maxn][2];
int dp(int x, int y, bool onY) {
    if (memo[x][y][onY] != -1) return memo[x][y][onY];
    int best = 1;

    for (int i : adj[onY ? y : x]) {
        bool legal = false;
        if (x < y) {
            if (x < i && i < y) {
                legal = true;
            }
        } else {
            if (i > x || i < y) {
                legal = true;
            }
        }
        if (!legal) continue;

        best = max(best, 1 + max(dp(x, i, 1), dp(i, y, 0)));
    }

    return memo[x][y][onY] = best;
}

// path[i][x] = longest path to x starting from i, going counterclockwise
int path[maxn][maxn];
// going clockwise
int pathRev[maxn][maxn];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;
    F0R(i, n) {
        int x;
        while (cin >> x && x != 0) {
            --x;
            adj[i].pb(x);
        }
    }

    int best = -1, bestIdx = -1;

    F0R(i, n) F0R(j, n) F0R(k, 2) memo[i][j][k] = -1;

    F0R(i, n) {
        path[i][i] = pathRev[i][i] = 1;
        F0R(add, n) {
            int cur = (i+add)%n;
            if (path[i][cur] == 0) continue;
            for (int nxt : adj[cur]) {
                if ((cur >= i && (nxt > cur || nxt < i)) || (cur <= i && (cur < nxt && nxt < i))) {
                        path[i][nxt] = max(path[i][nxt], path[i][cur]+1);
                }
            }
        }
        F0R(subtract, n) {
            int cur = (i-subtract+n)%n;
            if (pathRev[i][cur] == 0) continue;
            for (int nxt : adj[cur]) {
                if ((cur >= i && (i < nxt && nxt < cur)) || (cur <= i && (nxt > i || nxt < cur))) {
                    if (pathRev[i][cur] != 0)
                        pathRev[i][nxt] = max(pathRev[i][nxt], pathRev[i][cur]+1);
                }
            }
        }
    }
    /*
    F0R(i, n) {
        F0R(j, n) cout << "pathRev[" << i << "][" << j << "] = " << pathRev[i][j] << endl;
    }
    */

    F0R(i, n) {
        for (int j : adj[i]) {
            int val = max(dp(i, j, 1), dp(j, i, 0));

            if (k) {
                F0R(add, n) {
                    int cur = (i+add)%n;
                    int newVal = -1;
                    int newVal2 = -1;

                    if ((j > i && (i < cur && cur < j)) || (j < i && (cur > i || cur < j))) {
                        newVal = path[j][cur] + max(dp(cur, j, 0), dp(i, cur, 1)) - 1;
                    } else if (cur != i && cur != j) {
                        newVal2 = pathRev[j][cur] + max(dp(j, cur, 1), dp(cur, i, 0)) - 1;
                    }

                    val = max(val, max(newVal, newVal2));
                }
            }

            if (best < val) {
                best = val;
                bestIdx = i;
            }
        }
    }

    cout << best << endl;
    cout << bestIdx+1 << endl;

    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Incorrect	1 ms	492 KB	Output isn't correct
3	Incorrect	1 ms	620 KB	Output isn't correct
4	Incorrect	1 ms	620 KB	Output isn't correct
5	Correct	2 ms	748 KB	Output is correct
6	Incorrect	3 ms	876 KB	Output isn't correct
7	Correct	6 ms	1004 KB	Output is correct
8	Incorrect	5 ms	1004 KB	Output isn't correct
9	Correct	8 ms	1132 KB	Output is correct
10	Correct	22 ms	1260 KB	Output is correct
11	Correct	11 ms	1132 KB	Output is correct
12	Incorrect	55 ms	2028 KB	Output isn't correct
13	Incorrect	108 ms	2796 KB	Output isn't correct
14	Correct	96 ms	3564 KB	Output is correct
15	Incorrect	590 ms	4460 KB	Output isn't correct
16	Incorrect	755 ms	4712 KB	Output isn't correct
17	Incorrect	603 ms	4576 KB	Output isn't correct
18	Correct	118 ms	4332 KB	Output is correct
19	Incorrect	915 ms	4844 KB	Output isn't correct
20	Incorrect	918 ms	4760 KB	Output isn't correct