Submission #699045

#	Time	Username	Problem	Language	Result	Execution time	Memory
699045		dxz05	Catfish Farm (IOI22_fish)	C++17	0 / 100	1127 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define MP make_pair

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

    for (int i = 0; i < N; i++){
        sort(fish[i].begin(), fish[i].end());
        int k = (int)fish[i].size();
        sum[i].resize(k);
        for (int j = 0; j < k; j++){
            sum[i][j] = fish[i][j].second;
            if (j > 0) sum[i][j] += sum[i][j - 1];
        }
    }

    function<ll(int, int, int)> get_sum = [&](int i, int l, int r){ // sum of fish with X = i, l <= Y <= r
        int pl = lower_bound(fish[i].begin(), fish[i].end(), MP(l, 0)) - fish[i].begin();
        int pr = lower_bound(fish[i].begin(), fish[i].end(), MP(r + 1, 0)) - fish[i].begin() - 1;
        if (pl > pr) return 0ll;
        return sum[i][pr] - (pl > 0 ? sum[i][pl - 1] : 0ll);
    };

    vector<vector<ll>> dp(N, vector<ll>(N + 1, 0));
    for (int i = 1; i < N; i++){
        for (int l = 0; l <= N; l++){
            for (int j = 0; j <= N; j++){
                dp[i][l] = max(dp[i][l], dp[i - 1][j] + get_sum(i - 1, j + 1, l));
            }
            for (int j = 0; j <= N; j++){
                if (i >= 2) dp[i][l] = max(dp[i][l], dp[i - 2][j] + get_sum(i - 1, 0, l));
            }
        }
    }

    ll res = 0;
    for (int l = 0; l < N; l++){
        res = max(res, dp[N - 1][l]);
    }

    for (int l = 0; l < N; l++){
        res = max(res, dp[N - 2][l] + get_sum(N - 1, 0, l));
    }

    return res;
}

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