Submission #842620

#	Time	Username	Problem	Language	Result	Execution time	Memory
842620		WLZ	Catfish Farm (IOI22_fish)	C++17	100 / 100	214 ms	76388 KiB

fish

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

const long long INF = (long long) 1e18;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector< vector< pair<int, long long> > > x(N + 1);
    for (int i = 0; i < M; i++) {
        x[X[i] + 1].push_back({Y[i], W[i]});
    }
    for (int i = 0; i <= N; i++) {
        x[i].push_back({-1, 0});
        sort(x[i].begin(), x[i].end());
        for (int j = 1; j < (int) x[i].size(); j++) x[i][j].second += x[i][j - 1].second;
    }
    vector< vector<int> > pos(N + 1);
    pos[0] = {0};
    for (int i = 1; i <= N; i++) {
        for (auto &p : x[i - 1]) pos[i].push_back(p.first + 1);
        if (i < N) for (auto &p : x[i + 1]) pos[i].push_back(p.first + 1);
        sort(pos[i].begin(), pos[i].end());
        pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
    }
    vector< vector< vector<long long> > > dp(N + 1);
    dp[0] = {{0, 0}};
    for (int i = 1; i <= N; i++) {
        dp[i].assign((int) pos[i].size(), vector<long long>(2, -INF));
        int ptr_h = 0, ptr_k = 0, ptr_h_2 = 0;
        long long mx = -INF;
        for (int j = 0; j < (int) pos[i].size(); j++) {
            int h = pos[i][j];
            while (ptr_h < (int) pos[i - 1].size() && pos[i - 1][ptr_h] <= h) {
                while (ptr_k < (int) x[i - 1].size() && x[i - 1][ptr_k].first < pos[i - 1][ptr_h]) ptr_k++;
                mx = max(mx, dp[i - 1][ptr_h][0] - (ptr_k > 0 ? x[i - 1][ptr_k - 1].second : 0));
                ptr_h++;
            }
            while (ptr_h_2 < (int) x[i - 1].size() && x[i - 1][ptr_h_2].first < h) ptr_h_2++;
            dp[i][j][0] = max(mx + (ptr_h_2 > 0 ? x[i - 1][ptr_h_2 - 1].second : 0), dp[i - 1][0][1]);
        }
        ptr_h = (int) pos[i - 1].size() - 1, ptr_k = (int) x[i].size() - 1,
        ptr_h_2 = (int) x[i].size() - 1, mx = -INF;
        for (int j = (int) pos[i].size() - 1; j >= 0; j--) {
            int h = pos[i][j];
            while (ptr_h >= 0 && pos[i - 1][ptr_h] >= h) {
                while (ptr_k >= 0 && x[i][ptr_k].first >= pos[i - 1][ptr_h]) ptr_k--;
                mx = max(mx, dp[i - 1][ptr_h][0] + (ptr_k >= 0 ? x[i][ptr_k].second : 0));
                mx = max(mx, dp[i - 1][ptr_h][1] + (ptr_k >= 0 ? x[i][ptr_k].second : 0));
                ptr_h--;
            }
            while (ptr_h_2 >= 0 && x[i][ptr_h_2].first >= h) ptr_h_2--;
            dp[i][j][1] = mx - (ptr_h_2 >= 0 ? x[i][ptr_h_2].second : 0);
        }
    }
    long long ans = 0;
    for (int j = 0; j < (int) dp[N].size(); j++) ans = max({ans, dp[N][j][0], dp[N][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