제출 #1362891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362891		erering	메기 농장 (IOI22_fish)	C++20	37 / 100	1097 ms	2162688 KiB

fish

#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<pair<int,int>>> fish(N);
    for (int i = 0; i < M; ++i) fish[X[i]].push_back({Y[i], W[i]});

    vector<vector<int>> vals(N);
    for (int c = 0; c < N; ++c) {
        vals[c].push_back(0);
        vals[c].push_back(N);
        for (int d = max(0, c - 1); d <= min(N - 1, c + 1); ++d) {
            for (auto [y, w] : fish[d]) {
                vals[c].push_back(y);
                vals[c].push_back(y + 1);
            }
        }
        sort(vals[c].begin(), vals[c].end());
        vals[c].erase(unique(vals[c].begin(), vals[c].end()), vals[c].end());
    }

    vector<vector<vector<int>>> gain(N);
    for (int c = 0; c < N; ++c) {
        int sz = vals[c].size();
        gain[c].assign(sz, vector<int>(sz, 0));
        for (int i = 0; i < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                int lo = vals[c][i];
                int hi = vals[c][j];
                if (lo > hi) swap(lo, hi);
                int s = 0;
                for (auto [y, w] : fish[c]) {
                    if (lo <= y && y < hi) s += w;
                }
                gain[c][i][j] = s;
            }
        }
    }

    const long long NEG = -(1LL << 60);

    vector<vector<long long>> dp(vals[0].size(), vector<long long>(vals[1].size(), NEG));
    for (int i = 0; i < (int)vals[0].size(); ++i) {
        for (int j = 0; j < (int)vals[1].size(); ++j) {
            int h0 = vals[0][i], h1 = vals[1][j];
            long long add = 0;
            for (auto [y, w] : fish[0]) {
                if (h0 <= y && h1 > y) add += w;
            }
            dp[i][j] = add;
        }
    }

    for (int c = 1; c + 1 < N; ++c) {
        int A = vals[c - 1].size();
        int B = vals[c].size();
        int C = vals[c + 1].size();

        vector<vector<long long>> ndp(B, vector<long long>(C, NEG));

        for (int b = 0; b < B; ++b) {
            vector<long long> best(C, NEG);

            for (int a = 0; a < A; ++a) {
                long long base = dp[a][b];
                if (base == NEG) continue;

                int hp = vals[c - 1][a];
                int hc = vals[c][b];

                for (int cc = 0; cc < C; ++cc) {
                    int hn = vals[c + 1][cc];
                    long long add = 0;

                    for (auto [y, w] : fish[c]) {
                        if (hc <= y && (hp > y || hn > y)) add += w;
                    }

                    best[cc] = max(best[cc], base + add);
                }
            }

            for (int cc = 0; cc < C; ++cc) ndp[b][cc] = best[cc];
        }

        dp.swap(ndp);
    }

    long long ans = 0;

    if (N == 2) {
        for (int i = 0; i < (int)vals[0].size(); ++i) {
            for (int j = 0; j < (int)vals[1].size(); ++j) {
                int h0 = vals[0][i], h1 = vals[1][j];
                long long cur = 0;
                for (auto [y, w] : fish[0]) if (h0 <= y && h1 > y) cur += w;
                for (auto [y, w] : fish[1]) if (h1 <= y && h0 > y) cur += w;
                ans = max(ans, cur);
            }
        }
        return ans;
    }

    int last = N - 1;
    for (int a = 0; a < (int)vals[N - 2].size(); ++a) {
        for (int b = 0; b < (int)vals[N - 1].size(); ++b) {
            long long cur = dp[a][b];
            if (cur == NEG) continue;

            int hp = vals[N - 2][a];
            int hc = vals[N - 1][b];

            for (auto [y, w] : fish[last]) {
                if (hc <= y && hp > y) cur += w;
            }

            ans = max(ans, cur);
        }
    }

    return ans;
}

• 서브태스크 1: 0 / 3
• 서브태스크 2: 0 / 6
• 서브태스크 3: 9 / 9
• 서브태스크 4: 14 / 14
• 서브태스크 5: 0 / 21
• 서브태스크 6: 0 / 17
• 서브태스크 7: 14 / 14
• 서브태스크 8: 0 / 16