Submission #1168508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168508		jj_master	Catfish Farm (IOI22_fish)	C++20	100 / 100	221 ms	43096 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<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));

    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]);
    }

    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;
    }

    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_high = [&](int i, int j) {
        return lower_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin();
    };
    
    auto get_low = [&](int i, int j) {
        return upper_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 1;
    };

    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_high(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_low(i - 2, j)]);
                    dp[s][0] = max(dp[s][0], t3[0][get_high(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_low(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];
        }

        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(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]);
    }

    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;
}

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