Submission #741868

#	Time	Username	Problem	Language	Result	Execution time	Memory
741868		fanwen	Catfish Farm (IOI22_fish)	C++17	100 / 100	204 ms	44620 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

long long max_weights(int numCol, int numCatfish, vector <int> cols, vector <int> rows, vector <int> weights) {
    vector <vector <pair <int, long long>>> atCol(numCol);
    REP(i, numCatfish) {
        atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
    }
    REP(i, numCol) {

        sort(ALL(atCol[i]));
        atCol[i].emplace_back(numCol, 0);
        long long pre = 0;
        for (auto &[_, x] : atCol[i]) {
            x += pre;
            pre = x;
        }
    }
    auto prefix_sum = [&] (int i, int cur) -> long long {
        assert(0 <= i && i < numCol);
        auto it = lower_bound(ALL(atCol[i]), make_pair(cur, -1ll));
        if(it != atCol[i].begin()) return prev(it) -> second;
        return 0;
    };
    vector <vector <vector <long long>>> dp(numCol, vector <vector <long long>>(2));
    REP(i, numCol) {
        dp[i][0].resize((int) atCol[i].size(), 0);
        dp[i][1].resize((int) atCol[i].size(), 0);
        long long Max = 0;
        if(i == 0) continue;
        for (int cur = (int) atCol[i].size() - 1, pre = (int) atCol[i - 1].size(); cur >= 0; cur--) {
            while(pre > 0 && atCol[i - 1][pre - 1].first >= atCol[i][cur].first) {
                pre--;
                maximize(Max, max(dp[i - 1][0][pre], dp[i - 1][1][pre]) + prefix_sum(i, atCol[i - 1][pre].first));
            }
            maximize(dp[i][0][cur], Max - prefix_sum(i, atCol[i][cur].first));
            // cout << i << " 0 " << atCol[i][cur].first << " " << Max << '\n';
        }
        Max = (i > 1 ? max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1]))) : 0);
        for (int cur = 0, pre = -1; cur < (int) atCol[i].size(); ++cur) {
            while(pre + 1 < (int) atCol[i - 1].size() && atCol[i - 1][pre + 1].first <= atCol[i][cur].first) {
                pre++;
                maximize(Max, dp[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].first));
            }
            // cout << cur << '\n';
            maximize(dp[i][1][cur], Max + prefix_sum(i - 1, atCol[i][cur].first));
            // cout << i << " 0 " << atCol[i][cur].first << " " << dp[i][1][cur] << '\n';
        }
    }

    return max(*max_element(ALL(dp[numCol - 1][0])), *max_element(ALL(dp[numCol - 1][1])));
}

• 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