Submission #836044

#	Time	Username	Problem	Language	Result	Execution time	Memory
836044		tengiz05	Catfish Farm (IOI22_fish)	C++17	100 / 100	906 ms	105320 KiB

fish

#include "fish.h"

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

constexpr int N = 3000;
constexpr i64 inf = 1E18;

void chmax(i64 &a, i64 b) {
    if (a < b) {
        a = b;
    }
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<pair<int, int>>> a(n);
    vector<map<int, int>> f(n);
    for (int i = 0; i < m; i++) {
        f[X[i]][Y[i]] += W[i];
        if (X[i] > 0) {
            f[X[i] - 1][Y[i]] += 0;
        }
        if (X[i] < n - 1) {
            f[X[i] + 1][Y[i]] += 0;
        }
    }
    
    
    for (int i = 0; i < n; i++) {
        for (auto [j, x] : f[i]) {
            a[i].push_back({j, x});
        }
    }
    
    vector<vector<i64>> pre(n);
    vector<vector<array<i64, 2>>> dp(n);
    for (int i = 0; i < n; i++) {
        int k = a[i].size();
        sort(a[i].begin(), a[i].end());
        pre[i].resize(k + 1);
        for (int j = 0; j < k; j++) {
            pre[i][j + 1] = pre[i][j] + a[i][j].second;
        }
        dp[i].resize(k + 1, {-inf, -inf});
    }
    
    for (int i = 0; i <= int(a[0].size()); i++) {
        dp[0][i][0] = dp[0][i][1] = 0;
    }
    
    for (int i = 1; i < n; i++) {
        i64 best = -inf;
        int sz = a[i].size();
        int j = 0;
        for (int k = 0; k <= sz; k++) {
            while (j < int(dp[i - 1].size()) && ((j == 0 ? -1 : a[i - 1][j - 1].first) <= (k == 0 ? -1 : a[i][k - 1].first))) {
                chmax(best, dp[i - 1][j][0] - pre[i - 1][j]);
                j++;
            }
            // chmax(best, dp[i - 1][k][0] - pre[i - 1][k]);
            // if (i == 2) {
                // cout << best << " " << pre[i - 1][k] << " h\n";
            // }
            if (k == 0) {
                chmax(dp[i][k][0], best);
            } else {
                int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i][k - 1].first, 2E9}) - a[i - 1].begin();
                chmax(dp[i][k][0], best + pre[i - 1][p]);
            }
        }
        best = -inf;
        j = a[i - 1].size();
        for (int k = sz; k >= 0; k--) {
            while (j >= 0 && ((j == 0 ? -1 : a[i - 1][j - 1].first) >= (k == 0 ? -1 : a[i][k - 1].first))) {
                if (j == 0) {
                    chmax(best, dp[i - 1][j][1]);
                } else {
                    int p = upper_bound(a[i].begin(), a[i].end(), pair<int, int>{a[i - 1][j - 1].first, 2E9}) - a[i].begin();
                    chmax(best, dp[i - 1][j][1] + pre[i][p]);
                }
                j--;
            }
            // if (i == 3)
            // cerr << "a " << k << " " << best << "\n";
            // chmax(best, dp[i - 1][k][1] + pre[i][k]);
            if (k == 0) {
                chmax(dp[i][k][1], best);
            } else {
                chmax(dp[i][k][1], best - pre[i][k]);
            }
        }
        // cerr << "F\n";
        if (i >= 2) {
            best = -inf;
            j = a[i - 2].size();
            for (int k = sz; k >= 0; k--) {
                while (j >= 0 && ((j == 0 ? -1 : a[i - 2][j - 1].first) >= (k == 0 ? -1 : a[i][k - 1].first))) {
                    if (j == 0) {
                        chmax(best, dp[i - 2][j][1]);
                    } else {
                        int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i - 2][j - 1].first, 2E9}) - a[i - 1].begin();
                        chmax(best, dp[i - 2][j][1] + pre[i - 1][p]);
                    }
                    j--;
                }
                // chmax(best, dp[i - 2][k][1] + pre[i - 1][k]);
                chmax(dp[i][k][0], best);
            }
            best = -inf;
            j = 0;
            for (int k = 0; k <= sz; k++) {
                while (j < int(dp[i - 2].size()) && ((j == 0 ? -1 : a[i - 2][j - 1].first) <= (k == 0 ? -1 : a[i][k - 1].first))) {
                    chmax(best, dp[i - 2][j][1]);
                    j++;
                }
                // chmax(best, dp[i - 2][k][1]);
                if (k == 0) {
                    chmax(dp[i][k][0], best);
                } else {
                    int p = upper_bound(a[i - 1].begin(), a[i - 1].end(), pair<int, int>{a[i][k - 1].first, 2E9}) - a[i - 1].begin();
                    chmax(dp[i][k][0], best + pre[i - 1][p]);
                }
            }
        }
        // cerr << "D\n";
        for (int j = 0; j <= sz; j++) {
            chmax(dp[i][j][1], dp[i][j][0]);
        }
        if (i + 1 < n)
            chmax(dp[i + 1][0][0], dp[i][0][1]);
    }
    // cout << dp[3][0][1] << "\n";
    // cout << dp[3][1][1] << "\n";
    
    i64 ans = 0;
    for (int i = 0; i <= int(a[n - 1].size()); i++) {
        ans = max(ans, dp[n - 1][i][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