Submission #1255852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255852		biank	Catfish Farm (IOI22_fish)	C++17	100 / 100	250 ms	93548 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

void chmax(ll &x, ll v) {
    if (x < v) x = v;
}

ll max_weights(int N, int M, vi X, vi Y, vi W) {
    vector<vi> pos(N, vi(1, 0));
    vector<vector<ii>> byCol(N);
    forn(i, M) {
        byCol[X[i]].eb(Y[i] + 1, W[i]);
        if (X[i] > 0) {
            pos[X[i] - 1].pb(Y[i] + 1);
        }
        if (X[i] < N - 1) {
            pos[X[i] + 1].pb(Y[i] + 1);
        }
        pos[X[i]].pb(Y[i] + 1);
    }
    vector<vll> cant(N);
    forn(i, N) {
        sort(all(byCol[i]));
        sort(all(pos[i]));
        pos[i].erase(unique(all(pos[i])), end(pos[i]));
        cant[i].resize(sz(pos[i]));
        int k = 0;
        ll sum = 0;
        forn(j, sz(pos[i])) {
            while (k < sz(byCol[i]) && byCol[i][k].fst <= pos[i][j]) {
                sum += byCol[i][k++].snd;
            }
            cant[i][j] = sum;
        }
    }
    vector<vector<vll>> dp(N);
    forn(i, N) {
        dp[i] = vector<vll>(sz(pos[i]), vll(2, 0));
        if (i == 0) continue;
        const int m = sz(pos[i - 1]);
        forn(j, m) chmax(dp[i][0][0], dp[i - 1][j][1]);
        forn(j, sz(pos[i])) chmax(dp[i][j][0], dp[i - 1][0][1]);
        int j = 0;
        ll maxPref = dp[i - 1][0][0] - cant[i - 1][0];
        forn(k, sz(pos[i])) {
            while (j + 1 < m && pos[i - 1][j + 1] <= pos[i][k]) {
                j++;
                chmax(maxPref, dp[i - 1][j][0] - cant[i - 1][j]);
            }
            chmax(dp[i][k][0], maxPref + cant[i - 1][j]);
        }
        j = m;
        ll maxSuff = 0;
        int jPrime = sz(pos[i]) - 1;
        dforn(k, sz(pos[i])) {
            while (j > 0 && pos[i - 1][j - 1] >= pos[i][k]) {
                j--;
                while (pos[i][jPrime] > pos[i - 1][j]) jPrime--;
                chmax(maxSuff, max(dp[i - 1][j][0], dp[i - 1][j][1]) + cant[i][jPrime]);
            }
            chmax(dp[i][k][1], maxSuff - cant[i][k]);
        }
    }
    ll ret = 0;
    forn(i, N) forn(j, sz(pos[i])) forn(k, 2) chmax(ret, dp[i][j][k]);
    return ret;
}

• 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