답안 #1090325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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