Submission #1226587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226587		ericl23302	Catfish Farm (IOI22_fish)	C++20	35 / 100	1157 ms	2162688 KiB

fish

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

using namespace std;

typedef long long ll;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vector<vector<ll>> vals(N, vector<ll>(N + 1, 0));
    for (int i = 0; i < M; ++i) vals[X[i]][Y[i] + 1] += W[i];
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= N; ++j) vals[i][j] += vals[i][j - 1];
    }

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1, 0)));
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            if (!i && !j) continue;
            dp[0][i][j] = LLONG_MIN / 2;
        }
    }

    for (int i = 0; i < N; ++i) {
        vector<vector<ll>> &prevDp = dp[i], &curDp = dp[i + 1];
        for (int prev = 0; prev <= N; ++prev) {
            ll cumulative = LLONG_MIN / 2, otherwise = LLONG_MIN / 2;
            for (int prev2 = 0; prev2 <= N; ++prev2) {
                cumulative = max(prevDp[prev2][prev], cumulative);
                if (i) otherwise = max(otherwise, prevDp[prev2][prev] - vals[i - 1][max(prev2, prev)]);
            }

            for (int cur = 0; cur <= N; ++cur) {
                // ll additional = max(0ll, vals[i][prev] - vals[i][cur]);
                // if (i && cur > max(prev2, prev)) additional += vals[i - 1][cur] - vals[i - 1][max(prev2, prev)];
                ll curBest = cumulative;
                if (i) curBest = max(curBest, vals[i - 1][cur] + otherwise);
                curDp[prev][cur] = max(curDp[prev][cur], curBest + max(0ll, vals[i][prev] - vals[i][cur]));
            }
        }
    }

    // for (auto &i : dp) {
    //     for (auto &j : i) {
    //         for (auto &k : j) cout << k << ' ';
    //         cout << '\n';
    //     }
    //     cout << '\n';
    // }

    ll res = 0;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) res = max(res, dp[N][i][j]);
    }

    return res;
}

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