제출 #632829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632829		skittles1412	메기 농장 (IOI22_fish)	C++17	40 / 100	1081 ms	44720 KiB

fish

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(size(x))

ll max_weights(int n, vector<array<int, 3>> fish) {
    vector<pair<int, long>> arr[n];
    for (auto& [x, y, w] : fish) {
        arr[x].emplace_back(y, w);
    }
    for (auto& a : arr) {
        sort(begin(a), end(a));
        long psum = 0;
        for (auto& [_, x] : a) {
            psum += x;
            x = psum;
        }
    }
    auto ibs = [&](int i) -> bool {
        return 0 <= i && i < n;
    };
    auto psum = [&](int i, int x) -> long {
        if (!ibs(i)) {
            return 0;
        }
        auto it =
            lower_bound(begin(arr[i]), end(arr[i]), pair<int, long> {x, 0});
        if (it == arr[i].begin()) {
            return 0;
        }
        return (--it)->second;
    };
    auto sum = [&](int i, int l, int r) -> long {
        return max(long(0), psum(i, r) - psum(i, l));
    };
    auto get = [&](int i, int j) -> int {
        if (!ibs(i)) {
            return 0;
        }
        if (j < sz(arr[i])) {
            return arr[i][j].first;
        } else {
            return n;
        }
    };
    vector<long> dp[n + 1][2];
    dp[n][0] = dp[n][1] = {0};
    for (int i = n - 1; i >= 0; i--) {
        int m = sz(arr[i]);
        {
            dp[i][0].resize(m + 1);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k < sz(dp[i + 1][0]); k++) {
                    dp[i][0][j] =
                        max({dp[i][0][j], dp[i + 1][1][k],
                             dp[i + 1][0][k] +
                                 sum(i + 1, get(i + 1, k), get(i, j))});
                }
            }
        }
        {
            dp[i][1].resize(m + 1);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k < sz(dp[i + 1][0]); k++) {
                    long x = max(
                        dp[i + 1][1][k],
                        dp[i + 1][0][k] + sum(i + 1, get(i + 1, k), get(i, j)));
                    dp[i][1][j] =
                        max(dp[i][1][j], x + sum(i, get(i, j), get(i + 1, k)));
                }
            }
        }
    }
    return *max_element(begin(dp[0][1]), end(dp[0][1]));
}

ll max_weights(int n, int m, vector<int> xs, vector<int> ys, vector<int> ws) {
    vector<array<int, 3>> arr;
    for (int i = 0; i < m; i++) {
        arr.push_back({xs[i], ys[i], ws[i]});
    }
    return max_weights(n, arr);
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16