Submission #1054149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054149		shiomusubi496	Catfish Farm (IOI22_fish)	C++17	100 / 100	150 ms	31320 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }


constexpr ll inf = 1e18;

template<class M>
class SegmentTree {
    using T = typename M::T;
    int n;
    vector<T> dat;

public:
    SegmentTree(int n_, T x) {
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(2 * n, x);
    }
    void set(int k, T x) {
        k += n;
        dat[k] = x;
        while (k > 1) {
            k /= 2;
            dat[k] = M::op(dat[2 * k], dat[2 * k + 1]);
        }
    }
    void apply(int k, T x) { set(k, M::op(dat[k + n], x)); }
    T prod(int l, int r) const {
        l += n; r += n;
        T lsm = M::id(), rsm = M::id();
        while (l < r) {
            if (l & 1) lsm = M::op(lsm, dat[l++]);
            if (r & 1) rsm = M::op(dat[--r], rsm);
            l >>= 1; r >>= 1;
        }
        return M::op(lsm, rsm);
    }
    T all_prod() const { return dat[1]; }
};

struct Max {
    using T = ll;
    static T op(T a, T b) { return max(a, b); }
    static T id() { return -inf; }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vector<vector<int>> P(N), Q(N);
    rep (i, M) P[X[i]].push_back(i);
    rep (i, N) sort(all(P[i]), [&](int i, int j) { return Y[i] < Y[j]; });
    rep (i, N) {
        Q[i] = P[i];
        reverse(all(Q[i]));
    }
    vector<ll> Hsm(N);
    rep (i, M) Hsm[X[i]] += W[i];
    vector<ll> dp0(N + 1, -inf), dp1(N + 1, -inf);
    dp1[0] = 0;
    dp0[0] = 0;
    SegmentTree<Max> seg1(N + 1, -inf), seg2(N + 1, -inf);
    rep (i, N) {
        // i 行目から LIS を始める
        if (i != N - 1) {
            seg1.apply(0, dp1[i]);
            for (auto k : P[i]) {
                ll t = seg1.prod(0, Y[k] + 1) + W[k];
                seg1.apply(Y[k] + 1, t);
            }
            chmax(dp0[i + 1], seg1.all_prod());
        }
        // i 行目が max なので、 i+1 行目から LDS をする
        
        if (i != N - 1) {
            seg2.set(N, dp0[i]);
            for (auto k : Q[i + 1]) {
                ll t = seg2.prod(Y[k] + 1, N + 1) + W[k];
                seg2.apply(Y[k], t);
            }
            chmax(dp1[i + 2], seg2.all_prod());
        }
        if (i + 1 < N) chmax(dp0[i + 2], dp0[i] + Hsm[i + 1]);
    }
    return max(*max_element(all(dp0)), *max_element(all(dp1)));
}

• 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