Submission #1054148

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1054148	2024-08-12T06:59:08 Z	shiomusubi496	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	16032 KB

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> seg(N + 1, -inf);
    rep (i, N) {
        // i 行目から LIS を始める
        if (i != N - 1) {
            seg.apply(0, dp1[i]);
            for (auto k : P[i]) {
                ll t = seg.prod(0, Y[k] + 1) + W[k];
                seg.apply(Y[k] + 1, t);
            }
            chmax(dp0[i + 1], seg.all_prod());
        }
        // i 行目が max なので、 i+1 行目から LDS をする
        {
            SegmentTree<Max> seg(N + 1, -inf);
            seg.set(N, dp0[i]);
            rep2 (j, i + 1, N) {
                for (auto k : Q[j]) {
                    ll t = seg.prod(Y[k] + 1, N + 1) + W[k];
                    seg.apply(Y[k], t);
                }
                chmax(dp1[j + 1], seg.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
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1039 ms	13512 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Execution timed out	1093 ms	16032 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1047 ms	11608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	10 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	6 ms	524 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	10 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	6 ms	524 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	196 ms	1948 KB	Output is correct
18	Correct	213 ms	2084 KB	Output is correct
19	Correct	197 ms	1884 KB	Output is correct
20	Correct	172 ms	1880 KB	Output is correct
21	Correct	184 ms	1884 KB	Output is correct
22	Correct	408 ms	3416 KB	Output is correct
23	Correct	46 ms	604 KB	Output is correct
24	Correct	142 ms	1368 KB	Output is correct
25	Correct	6 ms	344 KB	Output is correct
26	Correct	36 ms	600 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	10 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	6 ms	524 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	196 ms	1948 KB	Output is correct
18	Correct	213 ms	2084 KB	Output is correct
19	Correct	197 ms	1884 KB	Output is correct
20	Correct	172 ms	1880 KB	Output is correct
21	Correct	184 ms	1884 KB	Output is correct
22	Correct	408 ms	3416 KB	Output is correct
23	Correct	46 ms	604 KB	Output is correct
24	Correct	142 ms	1368 KB	Output is correct
25	Correct	6 ms	344 KB	Output is correct
26	Correct	36 ms	600 KB	Output is correct
27	Correct	228 ms	860 KB	Output is correct
28	Execution timed out	1042 ms	8016 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1047 ms	11608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1039 ms	13512 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #1054148

Compilation message