제출 #1269921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269921		antonn	메기 농장 (IOI22_fish)	C++20	40 / 100	1096 ms	38808 KiB

fish

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<vector<pi>> occ(n + 1);
    for (int i = 0; i < m; ++i) {
        occ[x[i]].push_back({y[i], w[i]});
    }
    for (int i = 0; i < n; ++i) occ[i].push_back({n, 0});
    for (int i = 0; i < n; ++i) sort(occ[i].begin(), occ[i].end());
    
    vector<vector<ll>> pref(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i].assign(occ[i].size(), 0);
        pref[i][0] = occ[i][0].S;
        for (int j = 1; j < occ[i].size(); ++j) pref[i][j] = pref[i][j - 1] + occ[i][j].S;
    }
    
    auto between = [&](int x, int l, int r) {
        ll ans = 0;
        for (auto [a, b] : occ[x]) if (l <= a && a <= r) ans += b;
        int low = 0, high = occ[x].size() - 1, sol = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (occ[x][mid].F <= r) {
                sol = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (sol == -1) return 0LL;
        int R = sol;
        low = 0, high = occ[x].size() - 1, sol = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (occ[x][mid].F >= l) {
                sol = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        int L = sol;
        return pref[x][R] - (L == 0 ? 0 : pref[x][L - 1]);
    };
    
    vector<vector<ll>> dp0(n + 1), dp1(n + 1);
    for (int i = 0; i < n; ++i) dp0[i].assign(occ[i].size(), 0);
    for (int i = 0; i < n; ++i) dp1[i].assign(occ[i].size(), 0);
    for (int i = 1; i < n; ++i) {
        // p[i] < p[i - 1]
        for (int j = 0; j < occ[i].size(); ++j) {
            for (int k = 0; k < occ[i - 1].size(); ++k) {
                if (occ[i - 1][k].F - 1 >= occ[i][j].F) {
                    ckmax(dp0[i][j], dp0[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
                    ckmax(dp0[i][j], dp1[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
                }
            }
        }
        // p[i] > p[i - 1]
        for (int j = 0; j < occ[i].size(); ++j) {
            for (int k = 0; k < occ[i - 1].size(); ++k) {
                if (occ[i - 1][k].F - 1 <= occ[i][j].F - 1) {
                    ckmax(dp1[i][j], dp1[i - 1][k] + between(i - 1, occ[i - 1][k].F, occ[i][j].F - 1));
                }
            }
            if (i >= 2) {
                for (int k = 0; k < occ[i - 2].size(); ++k) {
                    ckmax(dp1[i][j], dp0[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 2][k].F - 1)));
                    ckmax(dp1[i][j], dp1[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 2][k].F - 1)));
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp0[n - 1][i]);
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp1[n - 1][i]);
    return ans;
}

• 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