답안 #982585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982585 2024-05-14T12:57:48 Z PanosPask Sailing Race (CEOI12_race) C++14
45 / 100
1692 ms 5200 KB
/*This problem needs arrays instad of vectors due to
extremely tight ML and TL*/

#include <bits/stdc++.h>
#define pb push_back
#define MOD(var, M) (((var) >= (M)) ? ((var) - M) : (var))

using namespace std;

const int MAXN = 500;
const int INF = 1e9;

int N, K;
bool stage[MAXN][MAXN];

vector<vector<int>> adj_list;

// dp[l][r][k]:  Maximum number of stages if enclosed by l, r
// and being in the stages such that l < s < r'
// Where r' = l > r ? r = r + N : r

// k == 0: Starting in l
// k == 1: Starting in r
int dp[MAXN][MAXN][2];

// Before the intersection with the first stage
// You can only choose one way to follow
// Either from l to r or from r to l
int bef[MAXN][MAXN][2];

int main(void)
{
    scanf("%d %d", &N, &K);

    adj_list.resize(N);

    for (int i = 0; i < N; i++) {
        int v;
        scanf("%d", &v);

        while (v != 0) {
            v--;
            stage[i][v] = true;
            adj_list[i].pb(v);
            adj_list[i].pb(v + N);
            scanf("%d", &v);
        }

        sort(adj_list[i].begin(), adj_list[i].end());
    }

    for (int len = 1; len <= N; len++) {
        for (int l = 0; l < N; l++) {
            int r_actual = l + len - 1;
            int r = MOD(r_actual, N);

            bef[l][r][0] = bef[l][r][1] = -INF;

            for (int i_actual = l + 1; i_actual < r_actual; i_actual++) {
                int i = MOD(i_actual, N);

                dp[l][r][0] = max(dp[l][r][0], dp[l][i][0]);
                dp[l][r][1] = max(dp[l][r][1], dp[i][r][1]);

                if (bef[l][i][0] != -INF && bef[i][r][0] != -INF) {
                    bef[l][r][0] = max(bef[l][r][0], bef[l][i][0] + bef[i][r][0]);
                }
                if (bef[l][i][1] != -INF && bef[i][r][1] != -INF) {
                    bef[l][r][1] = max(bef[l][r][1], bef[l][i][1] + bef[i][r][1]);
                }

                if (stage[l][i]) {
                    dp[l][r][0] = max(dp[l][r][0], 1 + dp[i][r][0]);
                }
                if (stage[r][i]) {
                    dp[l][r][1] = max(dp[l][r][1], 1 + dp[l][i][1]);
                }
            }

            if (stage[l][r]) {
                int res = 1 + dp[MOD(l + 1, N)][r][1];
                if (res >= dp[l][r][0]) {
                    dp[l][r][0] = res;
                }

                bef[l][r][0] = max(bef[l][r][0], 1);
            }
            if (stage[r][l]) {
                int res = 1 + dp[l][MOD(r_actual - 1, N)][0];
                if (res >= dp[l][r][1]) {
                    dp[l][r][1] = res;
                }

                bef[l][r][1] = max(bef[l][r][1], 1);
            }
        }
    }

    int ans = 0;
    int starting = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j][0] > ans) {
                ans = dp[i][j][0];
                starting = i;
            }
            if (dp[i][j][1] > ans) {
                ans = dp[i][j][1];
                starting = j;
            }
        }
    }
    if (K == 0) {
        printf("%d\n%d\n", ans, starting + 1);
        return 0;
    }

    // Unite bef(before intersection) with dp(after intersection)
    for (int len = 0; len <= N; len++) {
        for (int l = 0; l < N; l++) {
            int r_actual = l + len - 1;
            int r = MOD(r_actual, N);

            bool g1 = stage[l][r];
            bool g2 = stage[r][l];

            for (int i_actual = l + 1; i_actual < r_actual; i_actual++) {
                int i = MOD(i_actual, N);

                int res = -INF;
                int s = -1;
                if (g1) {
                    res = bef[l][i][0];
                    s = l;
                }
                if (g2 && res < bef[i][r][1]) {
                    res = bef[i][r][1];
                    s = r;
                }
                res++;

                if (res < 0) {
                    continue;
                }

                int j1 = upper_bound(adj_list[i].begin(), adj_list[i].end(), r_actual) - adj_list[i].begin();
                int j2 = lower_bound(adj_list[i].begin(), adj_list[i].end(), N + l) - adj_list[i].begin() - 1;

                int v = 0;
                if (j1 < adj_list[i].size()) {
                    int n1 = adj_list[i][j1];
                    if (n1 < l + N) {
                        v = max(v, 1 + dp[MOD(n1, N)][MOD(l - 1 + N, N)][0]);
                    }
                }
                if (j2 >= 0) {
                    int n2 = adj_list[i][j2];
                    if (n2 > r_actual) {
                        v = max(v, 1 + dp[MOD(r + 1, N)][MOD(n2, N)][1]);
                    }
                }

                if (ans < v + res) {
                    ans = v + res;
                    starting = s;
                }
            }
        }
    }

    printf("%d\n%d\n", ans, starting);

    return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:150:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |                 if (j1 < adj_list[i].size()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
race.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
race.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |             scanf("%d", &v);
      |             ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Correct 1 ms 2652 KB Output is correct
6 Incorrect 4 ms 2652 KB Output isn't correct
7 Correct 3 ms 2652 KB Output is correct
8 Incorrect 6 ms 2652 KB Output isn't correct
9 Correct 6 ms 2840 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 8 ms 2652 KB Output is correct
12 Incorrect 91 ms 3340 KB Output isn't correct
13 Correct 222 ms 3812 KB Output is correct
14 Correct 274 ms 4188 KB Output is correct
15 Incorrect 1166 ms 4872 KB Output isn't correct
16 Incorrect 1458 ms 5200 KB Output isn't correct
17 Incorrect 1190 ms 4876 KB Output isn't correct
18 Correct 543 ms 4952 KB Output is correct
19 Incorrect 1666 ms 5200 KB Output isn't correct
20 Incorrect 1692 ms 5088 KB Output isn't correct