Submission #1090325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090325	2024-09-18T08:43:42 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	60 / 100	3000 ms	4444 KB

race

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k, i, j, l, r, d, t, u;
    cin >> n >> k;
    vector<vector<int> > le(n), ri(n), dle(n), dri(n);
    vector<vector<bool> > w(n);
    for (i = 0; i < n; i++)
    {
        le[i].resize(n);
        ri[i].resize(n);
        dle[i].resize(n);
        dri[i].resize(n);
        w[i].resize(n);
        for (j = 0; j < n; j++)
            w[i][j] = 0;
        while (1)
        {
            cin >> d;
            if (!d)
                break;
            w[i][d - 1] = 1;
        }
    }
    for (i = 0; i < n; i++)
    {
        for (l = 0; l < n; l++)
        {
            r = (l + i) % n;
            le[l][r] = ri[l][r] = 0;
            if (i)
                dle[l][r] = dri[l][r] = 0;
            else
                dle[l][r] = dri[l][r] = -1;
            if (w[l][r])
                dle[l][r] = 1;
            if (w[r][l])
                dri[l][r] = 1;
            for (j = 1; j < i; j++)
            {
                d = (l + j) % n;
                t = max(ri[l][d], le[d][r]) + 1;
                if (w[l][d])
                {
                    le[l][r] = max(le[l][r], t);
                    dle[l][r] = max(dle[l][r], dle[d][r] + 1);
                }
                if (w[r][d])
                {
                    ri[l][r] = max(ri[l][r], t);
                    dri[l][r] = max(dri[l][r], dri[l][d] + 1);
                }
            }
        }
    }
    t = u = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (!w[i][j])
                continue;
            d = max(ri[i][j], le[j][i]) + 1;
            if (d > t)
            {
                t = d;
                u = i;
            }
        }
    }
    if (k)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if (!w[i][j])
                    continue;
                for (l = i + 1;; l++)
                {
                    if (l >= n)
                        l -= n;
                    if (l == j)
                        break;
                    for (r = j + 1;; r++)
                    {
                        if (r >= n)
                            r -= n;
                        if (r == i)
                            break;
                        if (!w[l][r])
                            continue;
                        d = max(dri[l][j] + max(ri[j][r], le[r][i]), dle[j][r] + max(ri[i][l], le[l][j])) + 2;
                        if (d > t)
                        {
                            t = d;
                            u = i;
                        }
                    }
                }
            }
        }
    }
    cout << t << "\n" << u + 1;
    return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	4 ms	524 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	5 ms	572 KB	Output is correct
9	Correct	6 ms	604 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	9 ms	604 KB	Output is correct
12	Incorrect	141 ms	1116 KB	Output isn't correct
13	Incorrect	352 ms	1908 KB	Output isn't correct
14	Correct	142 ms	2904 KB	Output is correct
15	Execution timed out	3073 ms	4440 KB	Time limit exceeded
16	Execution timed out	3084 ms	4440 KB	Time limit exceeded
17	Execution timed out	3040 ms	4440 KB	Time limit exceeded
18	Correct	253 ms	4440 KB	Output is correct
19	Execution timed out	3071 ms	4444 KB	Time limit exceeded
20	Execution timed out	3025 ms	4300 KB	Time limit exceeded