제출 #1168504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168504		jj_master	메기 농장 (IOI22_fish)	C++20	컴파일 에러	0 ms	0 KiB

fish

int max_weights(int N, int M, vector<int> &X, vector<int> &Y, vector<int> &W)
{
    // Initialize DP, pref, sp, t1, t2, t3, t4
    vector<vector<long long>> DP(N + 1, vector<long long>(2, 0ll));
    vector<vector<pair<int, long long>>> pref(N + 2);
    for (int i = 0; i <= N + 1; i++) pref[i].emplace_back(0, 0);
    vector<vector<int>> sp(N + 2);
    for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(0);
    for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(N);
    
    vector<vector<long long>> t1(2, vector<long long>(N + 1, 0ll));
    vector<vector<long long>> t2(3, vector<long long>(N + 1, 0ll));
    vector<vector<long long>> t3(3, vector<long long>(N + 1, 0ll));
    vector<vector<long long>> t4(2, vector<long long>(N + 1, 0ll));

    // Populate the pref and sp arrays
    for (int i = 0; i < M; i++) {
        pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
        sp[X[i] + 1].emplace_back(Y[i]);
    }

    // Sort and process the pref and sp arrays
    for (int i = 1; i <= N + 1; i++) {
        sort(sp[i].begin(), sp[i].end());
        sp[i].erase(unique(sp[i].begin(), sp[i].end()), sp[i].end());
        sort(pref[i].begin(), pref[i].end());
        for (int j = 1; j < pref[i].size(); j++) pref[i][j].second += pref[i][j - 1].second;
    }

    // Lambda functions to get prefix sum and find boundaries
    auto getpref = [&](int i, int j) {
        auto iter = lower_bound(pref[i].begin(), pref[i].end(), make_pair(j + 1, -1ll));
        iter--;
        return iter->second;
    };

    auto get_higher = [&](int i, int j) {
        return lower_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 0;
    };

    auto get_lower = [&](int i, int j) {
        return upper_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 1;
    };

    // Main logic for DP
    for (int i = 2; i <= N; i++) {
        int tot = sp[i].size() - 1;
        for (int s = 0; s <= tot; s++) {
            int j = sp[i][s];
            if (i != 2) DP[s][1] = max(DP[s][1], -getpref(i, j) + t1[0][get_higher(i - 1, j)]);
            else DP[s][1] = max(DP[s][1], getpref(i, N) - getpref(i, j));
            
            if (i > 2) {
                if (i != 3) {
                    DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t2[0][get_lower(i - 2, j)]);
                    DP[s][0] = max(DP[s][0], t3[0][get_higher(i - 2, j)]);
                } else DP[s][0] = max(DP[s][0], getpref(i - 1, N));
            }

            if (i != 2) DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t4[0][get_lower(i - 1, j)]);
            else DP[s][0] = max(DP[s][0], getpref(i - 1, j));

            t1[1][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
            t2[2][s] = max(DP[s][0], DP[s][1]);
            t3[2][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
            t4[1][s] = -getpref(i, j) + DP[s][0];
        }

        // Update the t1, t2, t3, t4 vectors
        for (int j = tot - 1; j >= 0; j--) t1[1][j] = max(t1[1][j], t1[1][j + 1]);
        for (int j = 1; j <= tot; j++) t2[2][j] = max(t2[2][j], t2[2][j - 1]);
        for (int j = tot - 1; j >= 0; j--) t3[2][j] = max(t3[2][j], t3[2][j + 1]);
        for (int j = 1; j <= tot; j++) t4[1][j] = max(t4[1][j], t4[1][j - 1]);

        // Swap to prepare for the next iteration
        swap(t1[0], t1[1]);
        swap(t2[0], t2[1]);
        swap(t2[1], t2[2]);
        swap(t3[0], t3[1]);
        swap(t3[1], t3[2]);
        swap(t4[0], t4[1]);
    }

    // Find the maximum value from the DP array
    long long ans = 0;
    for (int j = 0; j <= N; j++) ans = max(ans, DP[j][0]);
    for (int j = 0; j <= N; j++) ans = max(ans, DP[j][1]);

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp:1:31: error: 'vector' has not been declared
    1 | int max_weights(int N, int M, vector<int> &X, vector<int> &Y, vector<int> &W)
      |                               ^~~~~~
fish.cpp:1:37: error: expected ',' or '...' before '<' token
    1 | int max_weights(int N, int M, vector<int> &X, vector<int> &Y, vector<int> &W)
      |                                     ^
fish.cpp: In function 'int max_weights(int, int, int)':
fish.cpp:4:12: error: 'vector' was not declared in this scope
    4 |     vector<vector<long long>> DP(N + 1, vector<long long>(2, 0ll));
      |            ^~~~~~
fish.cpp:4:19: error: expected primary-expression before 'long'
    4 |     vector<vector<long long>> DP(N + 1, vector<long long>(2, 0ll));
      |                   ^~~~
fish.cpp:5:19: error: 'pair' was not declared in this scope
    5 |     vector<vector<pair<int, long long>>> pref(N + 2);
      |                   ^~~~
fish.cpp:5:24: error: expected primary-expression before 'int'
    5 |     vector<vector<pair<int, long long>>> pref(N + 2);
      |                        ^~~
fish.cpp:6:38: error: 'pref' was not declared in this scope
    6 |     for (int i = 0; i <= N + 1; i++) pref[i].emplace_back(0, 0);
      |                                      ^~~~
fish.cpp:7:19: error: expected primary-expression before 'int'
    7 |     vector<vector<int>> sp(N + 2);
      |                   ^~~
fish.cpp:8:38: error: 'sp' was not declared in this scope
    8 |     for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(0);
      |                                      ^~
fish.cpp:9:38: error: 'sp' was not declared in this scope
    9 |     for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(N);
      |                                      ^~
fish.cpp:11:19: error: expected primary-expression before 'long'
   11 |     vector<vector<long long>> t1(2, vector<long long>(N + 1, 0ll));
      |                   ^~~~
fish.cpp:12:19: error: expected primary-expression before 'long'
   12 |     vector<vector<long long>> t2(3, vector<long long>(N + 1, 0ll));
      |                   ^~~~
fish.cpp:13:19: error: expected primary-expression before 'long'
   13 |     vector<vector<long long>> t3(3, vector<long long>(N + 1, 0ll));
      |                   ^~~~
fish.cpp:14:19: error: expected primary-expression before 'long'
   14 |     vector<vector<long long>> t4(2, vector<long long>(N + 1, 0ll));
      |                   ^~~~
fish.cpp:18:9: error: 'pref' was not declared in this scope
   18 |         pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
      |         ^~~~
fish.cpp:18:14: error: 'X' was not declared in this scope
   18 |         pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
      |              ^
fish.cpp:18:37: error: 'Y' was not declared in this scope
   18 |         pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
      |                                     ^
fish.cpp:18:47: error: 'W' was not declared in this scope
   18 |         pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
      |                                               ^
fish.cpp:19:9: error: 'sp' was not declared in this scope
   19 |         sp[X[i] + 1].emplace_back(Y[i]);
      |         ^~
fish.cpp:24:14: error: 'sp' was not declared in this scope
   24 |         sort(sp[i].begin(), sp[i].end());
      |              ^~
fish.cpp:24:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   24 |         sort(sp[i].begin(), sp[i].end());
      |         ^~~~
      |         short
fish.cpp:25:21: error: 'unique' was not declared in this scope
   25 |         sp[i].erase(unique(sp[i].begin(), sp[i].end()), sp[i].end());
      |                     ^~~~~~
fish.cpp:26:14: error: 'pref' was not declared in this scope
   26 |         sort(pref[i].begin(), pref[i].end());
      |              ^~~~
fish.cpp: In lambda function:
fish.cpp:32:33: error: 'pref' was not declared in this scope; did you mean 'getpref'?
   32 |         auto iter = lower_bound(pref[i].begin(), pref[i].end(), make_pair(j + 1, -1ll));
      |                                 ^~~~
      |                                 getpref
fish.cpp:32:65: error: 'make_pair' was not declared in this scope
   32 |         auto iter = lower_bound(pref[i].begin(), pref[i].end(), make_pair(j + 1, -1ll));
      |                                                                 ^~~~~~~~~
fish.cpp:32:21: error: 'lower_bound' was not declared in this scope
   32 |         auto iter = lower_bound(pref[i].begin(), pref[i].end(), make_pair(j + 1, -1ll));
      |                     ^~~~~~~~~~~
fish.cpp: In lambda function:
fish.cpp:38:28: error: 'sp' was not declared in this scope
   38 |         return lower_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 0;
      |                            ^~
fish.cpp:38:16: error: 'lower_bound' was not declared in this scope
   38 |         return lower_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 0;
      |                ^~~~~~~~~~~
fish.cpp: In lambda function:
fish.cpp:42:28: error: 'sp' was not declared in this scope
   42 |         return upper_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 1;
      |                            ^~
fish.cpp:42:16: error: 'upper_bound' was not declared in this scope
   42 |         return upper_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 1;
      |                ^~~~~~~~~~~
fish.cpp: In function 'int max_weights(int, int, int)':
fish.cpp:47:19: error: 'sp' was not declared in this scope
   47 |         int tot = sp[i].size() - 1;
      |                   ^~
fish.cpp:50:25: error: 'DP' was not declared in this scope
   50 |             if (i != 2) DP[s][1] = max(DP[s][1], -getpref(i, j) + t1[0][get_higher(i - 1, j)]);
      |                         ^~
fish.cpp:50:67: error: 't1' was not declared in this scope
   50 |             if (i != 2) DP[s][1] = max(DP[s][1], -getpref(i, j) + t1[0][get_higher(i - 1, j)]);
      |                                                                   ^~
fish.cpp:50:36: error: 'max' was not declared in this scope
   50 |             if (i != 2) DP[s][1] = max(DP[s][1], -getpref(i, j) + t1[0][get_higher(i - 1, j)]);
      |                                    ^~~
fish.cpp:51:18: error: 'DP' was not declared in this scope
   51 |             else DP[s][1] = max(DP[s][1], getpref(i, N) - getpref(i, j));
      |                  ^~
fish.cpp:51:29: error: 'max' was not declared in this scope
   51 |             else DP[s][1] = max(DP[s][1], getpref(i, N) - getpref(i, j));
      |                             ^~~
fish.cpp:55:21: error: 'DP' was not declared in this scope
   55 |                     DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t2[0][get_lower(i - 2, j)]);
      |                     ^~
fish.cpp:55:66: error: 't2' was not declared in this scope
   55 |                     DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t2[0][get_lower(i - 2, j)]);
      |                                                                  ^~
fish.cpp:55:32: error: 'max' was not declared in this scope
   55 |                     DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t2[0][get_lower(i - 2, j)]);
      |                                ^~~
fish.cpp:56:46: error: 't3' was not declared in this scope
   56 |                     DP[s][0] = max(DP[s][0], t3[0][get_higher(i - 2, j)]);
      |                                              ^~
fish.cpp:57:24: error: 'DP' was not declared in this scope
   57 |                 } else DP[s][0] = max(DP[s][0], getpref(i - 1, N));
      |                        ^~
fish.cpp:57:35: error: 'max' was not declared in this scope
   57 |                 } else DP[s][0] = max(DP[s][0], getpref(i - 1, N));
      |                                   ^~~
fish.cpp:60:25: error: 'DP' was not declared in this scope
   60 |             if (i != 2) DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t4[0][get_lower(i - 1, j)]);
      |                         ^~
fish.cpp:60:70: error: 't4' was not declared in this scope
   60 |             if (i != 2) DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t4[0][get_lower(i - 1, j)]);
      |                                                                      ^~
fish.cpp:60:36: error: 'max' was not declared in this scope
   60 |             if (i != 2) DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t4[0][get_lower(i - 1, j)]);
      |                                    ^~~
fish.cpp:61:18: error: 'DP' was not declared in this scope
   61 |             else DP[s][0] = max(DP[s][0], getpref(i - 1, j));
      |                  ^~
fish.cpp:61:29: error: 'max' was not declared in this scope
   61 |             else DP[s][0] = max(DP[s][0], getpref(i - 1, j));
      |                             ^~~
fish.cpp:63:13: error: 't1' was not declared in this scope
   63 |             t1[1][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
      |             ^~
fish.cpp:63:48: error: 'DP' was not declared in this scope
   63 |             t1[1][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
      |                                                ^~
fish.cpp:63:44: error: 'max' was not declared in this scope
   63 |             t1[1][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
      |                                            ^~~
fish.cpp:64:13: error: 't2' was not declared in this scope
   64 |             t2[2][s] = max(DP[s][0], DP[s][1]);
      |             ^~
fish.cpp:65:13: error: 't3' was not declared in this scope
   65 |             t3[2][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
      |             ^~
fish.cpp:66:13: error: 't4' was not declared in this scope
   66 |             t4[1][s] = -getpref(i, j) + DP[s][0];
      |             ^~
fish.cpp:70:44: error: 't1' was not declared in this scope
   70 |         for (int j = tot - 1; j >= 0; j--) t1[1][j] = max(t1[1][j], t1[1][j + 1]);
      |                                            ^~
fish.cpp:70:55: error: 'max' was not declared in this scope
   70 |         for (int j = tot - 1; j >= 0; j--) t1[1][j] = max(t1[1][j], t1[1][j + 1]);
      |                                                       ^~~
fish.cpp:71:40: error: 't2' was not declared in this scope
   71 |         for (int j = 1; j <= tot; j++) t2[2][j] = max(t2[2][j], t2[2][j - 1]);
      |                                        ^~
fish.cpp:71:51: error: 'max' was not declared in this scope
   71 |         for (int j = 1; j <= tot; j++) t2[2][j] = max(t2[2][j], t2[2][j - 1]);
      |                                                   ^~~
fish.cpp:72:44: error: 't3' was not declared in this scope
   72 |         for (int j = tot - 1; j >= 0; j--) t3[2][j] = max(t3[2][j], t3[2][j + 1]);
      |                                            ^~
fish.cpp:72:55: error: 'max' was not declared in this scope
   72 |         for (int j = tot - 1; j >= 0; j--) t3[2][j] = max(t3[2][j], t3[2][j + 1]);
      |                                                       ^~~
fish.cpp:73:40: error: 't4' was not declared in this scope
   73 |         for (int j = 1; j <= tot; j++) t4[1][j] = max(t4[1][j], t4[1][j - 1]);
      |                                        ^~
fish.cpp:73:51: error: 'max' was not declared in this scope
   73 |         for (int j = 1; j <= tot; j++) t4[1][j] = max(t4[1][j], t4[1][j - 1]);
      |                                                   ^~~
fish.cpp:76:14: error: 't1' was not declared in this scope
   76 |         swap(t1[0], t1[1]);
      |              ^~
fish.cpp:76:9: error: 'swap' was not declared in this scope
   76 |         swap(t1[0], t1[1]);
      |         ^~~~
fish.cpp:77:14: error: 't2' was not declared in this scope
   77 |         swap(t2[0], t2[1]);
      |              ^~
fish.cpp:79:14: error: 't3' was not declared in this scope
   79 |         swap(t3[0], t3[1]);
      |              ^~
fish.cpp:81:14: error: 't4' was not declared in this scope
   81 |         swap(t4[0], t4[1]);
      |              ^~
fish.cpp:86:49: error: 'DP' was not declared in this scope
   86 |     for (int j = 0; j <= N; j++) ans = max(ans, DP[j][0]);
      |                                                 ^~
fish.cpp:86:40: error: 'max' was not declared in this scope
   86 |     for (int j = 0; j <= N; j++) ans = max(ans, DP[j][0]);
      |                                        ^~~
fish.cpp:87:49: error: 'DP' was not declared in this scope
   87 |     for (int j = 0; j <= N; j++) ans = max(ans, DP[j][1]);
      |                                                 ^~
fish.cpp:87:40: error: 'max' was not declared in this scope
   87 |     for (int j = 0; j <= N; j++) ans = max(ans, DP[j][1]);
      |                                        ^~~