Submission #1269946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269946		antonn	Catfish Farm (IOI22_fish)	C++20	100 / 100	193 ms	40212 KiB

fish

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<vector<pi>> occ(n + 1);
    for (int i = 0; i < m; ++i) {
        occ[x[i]].push_back({y[i], w[i]});
    }
    for (int i = 0; i < n; ++i) occ[i].push_back({n, 0});
    for (int i = 0; i < n; ++i) sort(occ[i].begin(), occ[i].end());
    
    vector<vector<ll>> pref(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i].assign(occ[i].size(), 0);
        pref[i][0] = occ[i][0].S;
        for (int j = 1; j < occ[i].size(); ++j) pref[i][j] = pref[i][j - 1] + occ[i][j].S;
    }
    
    auto under = [&](int x, int r) {
        int low = 0, high = occ[x].size() - 1, sol = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (occ[x][mid].F <= r) {
                sol = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (sol == -1) return 0LL;
        return pref[x][sol];
    };
    
    auto between = [&](int x, int l, int r) {
        return under(x, r) - under(x, l - 1);
    };
    
    vector<vector<ll>> dp0(n + 1), dp1(n + 1);
    for (int i = 0; i < n; ++i) dp0[i].assign(occ[i].size(), 0);
    for (int i = 0; i < n; ++i) dp1[i].assign(occ[i].size(), 0);
    for (int i = 1; i < n; ++i) {
        // p[i] < p[i - 1]
        int ptr = occ[i - 1].size() - 1;
        ll mx = 0;
        for (int j = occ[i].size() - 1; j >= 0; --j) {
            while (ptr >= 0 && occ[i - 1][ptr].F - 1 >= occ[i][j].F) {
                ckmax(mx, max(dp0[i - 1][ptr], dp1[i - 1][ptr]) + under(i, occ[i - 1][ptr].F - 1)); 
                --ptr;
            }
            ckmax(dp0[i][j], mx - under(i, occ[i][j].F - 1));
        }
        // p[i] > p[i - 1]
        vector<ll> pref, suff;
        if (i >= 2) {
            pref.assign(occ[i - 2].size() + 1, -1e18);
            suff.assign(occ[i - 2].size() + 1, -1e18);
            pref[0] = max(dp0[i - 2][0], dp1[i - 2][0]);
            for (int j = 1; j < occ[i - 2].size(); ++j) {
                pref[j] = max(pref[j - 1], max(dp0[i - 2][j], dp1[i - 2][j]));
            }
            for (int j = occ[i - 2].size() - 1; j >= 0; --j) {
                suff[j] = max(suff[j + 1], max(dp0[i - 2][j], dp1[i - 2][j]) + under(i - 1, occ[i - 2][j].F - 1));
            }
        }
        ptr = 0;
        mx = -1e18;
        for (int j = 0; j < occ[i].size(); ++j) {
            while (ptr < occ[i - 1].size() && occ[i - 1][ptr].F <= occ[i][j].F) {
                ckmax(mx, dp1[i - 1][ptr] - under(i - 1, occ[i - 1][ptr].F - 1));
                ++ptr;
            }
            ckmax(dp1[i][j], mx + under(i - 1, occ[i][j].F - 1));
            if (i >= 2) {
                int low = 0, high = occ[i - 2].size() - 1, sol = -1;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (occ[i - 2][mid].F <= occ[i][j].F) {
                        sol = mid;
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
                if (sol != -1) {
                    ckmax(dp1[i][j], under(i - 1, occ[i][j].F - 1) + pref[sol]);
                }
                ckmax(dp1[i][j], suff[sol + 1]);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp0[n - 1][i]);
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp1[n - 1][i]);
    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