Submission #1090421

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090421	2024-09-18T10:52:31 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	55 / 100	3000 ms	4696 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;
                        d = 0;
                        if (w[l][r])
                            d = max(d, dri[l][j] + max(ri[j][r], le[r][i]) + 2);
                        if (w[r][l])
                            d = max(d, 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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	344 KB	Output isn't correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	4 ms	528 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	6 ms	576 KB	Output is correct
9	Correct	5 ms	600 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	8 ms	604 KB	Output is correct
12	Incorrect	196 ms	1136 KB	Output isn't correct
13	Incorrect	479 ms	1880 KB	Output isn't correct
14	Correct	139 ms	2908 KB	Output is correct
15	Execution timed out	3055 ms	4444 KB	Time limit exceeded
16	Execution timed out	3034 ms	4440 KB	Time limit exceeded
17	Execution timed out	3018 ms	4696 KB	Time limit exceeded
18	Correct	255 ms	4440 KB	Output is correct
19	Execution timed out	3088 ms	4440 KB	Time limit exceeded
20	Execution timed out	3022 ms	4440 KB	Time limit exceeded