Submission #95444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95444	2019-02-01T08:37:33 Z	forestryks	Sailing Race (CEOI12_race)	C++14	95 / 100	1904 ms	4760 KB

race

///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
////////////////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 505;
int n, k;
bool g[MAXN][MAXN];
int dp[MAXN][MAXN];
int dpc[MAXN][MAXN];
int ds[MAXN][MAXN];
int dsc[MAXN][MAXN];

inline int md(int x) {
    if (x >= n) return x - n;
    if (x < 0) return x + n;
    return x;
}

int f(int, int);
int fc(int, int);

int f(int a, int b) {
    if (dp[a][b] != -1) return dp[a][b];

    dp[a][b] = 0;
    for (int i = md(b + 1); i != a; i = md(i + 1)) {
        if (g[b][i]) dp[a][b] = max(dp[a][b], max(fc(b, i), f(a, i)) + 1);
    }

    return dp[a][b];
}

int fc(int a, int b) {
    if (dpc[a][b] != -1) return dpc[a][b];

    dpc[a][b] = 0;
    for (int i = md(b - 1); i != a; i = md(i - 1)) {
        if (g[b][i]) dpc[a][b] = max(dpc[a][b], max(f(b, i), fc(a, i)) + 1);
    }

    return dpc[a][b];
}

int s(int a, int b) {
    if (ds[a][b] != -2) return ds[a][b];

    ds[a][b] = -1;
    if (a == b) ds[a][b] = 0;
    if (g[a][b]) ds[a][b] = 1;
    for (int i = md(a + 1); i != b; i = md(i + 1)) {
        int ai = s(a, i);
        int ib = s(i, b);
        if (ai == -1 || ib == -1) continue;
        ds[a][b] = max(ds[a][b], ai + ib);
    }

    return ds[a][b];
}

int sc(int a, int b) {
    if (dsc[a][b] != -2) return dsc[a][b];

    dsc[a][b] = -1;
    if (a == b) dsc[a][b] = 0;
    if (g[a][b]) dsc[a][b] = 1;
    for (int i = md(a - 1); i != b; i = md(i - 1)) {
        int ai = sc(a, i);
        int ib = sc(i, b);
        if (ai == -1 || ib == -1) continue;
        dsc[a][b] = max(dsc[a][b], ai + ib);
    }

    return dsc[a][b];
}

int main() {
    FAST_IO;
    cin >> n >> k;
    rep(i, n) {
        while (true) {
            int x;
            cin >> x;
            x--;
            if (x == -1) break;
            g[i][x] = true;
        }
    }

    rep(i, n) {
        rep(j, n) {
            dp[i][j] = dpc[i][j] = -1;
            ds[i][j] = dsc[i][j] = -2;
        }
    }

    int res = 0;
    int st = 0;
    rep(i, n) {
        rep(j, n) {
            if (i == j) continue;
            if (g[i][j]) {
                int nw = max(f(i, j), fc(i, j)) + 1;
                if (nw > res) {
                    res = nw;
                    st = i;
                }
            }
        }
    }

    rep(b, n) {
        rep(c, n) {
            if (b == c) continue;
            if (s(b, c) == -1) continue;

            int a;
            for (a = md(c + 1); a != b; a = md(a + 1)) {
                if (g[a][b]) break;
            }

            if (a == b) continue;

            for (int d = md(a + 1); d != b; d = md(d + 1)) {
                if (!g[c][d]) continue;
                int nw = 2 + s(b, c) + max(f(b, d), fc(a, d));
                if (nw > res) {
                    res = nw;
                    st = a;
                }
            }
        }
    }

    rep(b, n) {
        rep(c, n) {
            if (b == c) continue;
            if (sc(b, c) == -1) continue;

            int a;
            for (a = md(c - 1); a != b; a = md(a - 1)) {
                if (g[a][b]) break;
            }

            if (a == b) continue;

            for (int d = md(a - 1); d != b; d = md(d - 1)) {
                if (!g[c][d]) continue;
                int nw = 2 + sc(b, c) + max(fc(b, d), f(a, d));
                if (nw > res) {
                    res = nw;
                    st = a;
                }
            }
        }
    }


    cout << res << endl;
    cout << st + 1 << endl;
}

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	632 KB	Output is correct
4	Correct	3 ms	760 KB	Output is correct
5	Incorrect	4 ms	764 KB	Output isn't correct
6	Correct	6 ms	888 KB	Output is correct
7	Correct	9 ms	888 KB	Output is correct
8	Correct	10 ms	1016 KB	Output is correct
9	Correct	16 ms	1144 KB	Output is correct
10	Correct	18 ms	1144 KB	Output is correct
11	Correct	23 ms	1272 KB	Output is correct
12	Correct	123 ms	2040 KB	Output is correct
13	Correct	363 ms	2936 KB	Output is correct
14	Correct	820 ms	3964 KB	Output is correct
15	Correct	1701 ms	4528 KB	Output is correct
16	Correct	1862 ms	4760 KB	Output is correct
17	Correct	1880 ms	4728 KB	Output is correct
18	Correct	1505 ms	4728 KB	Output is correct
19	Correct	1904 ms	4744 KB	Output is correct
20	Correct	1875 ms	4728 KB	Output is correct