Submission #1054146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1054146	2024-08-12T06:56:36 Z	shiomusubi496	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	13944 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;
    rep (i, N) {
        // i 行目から LIS を始める
        {
            SegmentTree<Max> seg(N + 1, -inf);
            seg.set(0, dp1[i]);
            rep2 (j, i, N - 1) {
                for (auto k : P[j]) {
                    ll t = seg.prod(0, Y[k] + 1) + W[k];
                    seg.apply(Y[k] + 1, t);
                }
                chmax(dp0[j + 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	1067 ms	11360 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	348 KB	Output is correct
2	Execution timed out	1096 ms	13944 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	1070 ms	9308 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	20 ms	552 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	512 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	8 ms	508 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	20 ms	552 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	512 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	8 ms	508 KB	Output is correct
15	Correct	3 ms	348 KB	Output is correct
16	Correct	6 ms	516 KB	Output is correct
17	Correct	428 ms	2716 KB	Output is correct
18	Correct	438 ms	2652 KB	Output is correct
19	Correct	321 ms	2792 KB	Output is correct
20	Correct	321 ms	2648 KB	Output is correct
21	Correct	330 ms	2780 KB	Output is correct
22	Correct	777 ms	5120 KB	Output is correct
23	Correct	101 ms	860 KB	Output is correct
24	Correct	313 ms	1884 KB	Output is correct
25	Correct	10 ms	348 KB	Output is correct
26	Correct	82 ms	888 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	20 ms	552 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	512 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	8 ms	508 KB	Output is correct
15	Correct	3 ms	348 KB	Output is correct
16	Correct	6 ms	516 KB	Output is correct
17	Correct	428 ms	2716 KB	Output is correct
18	Correct	438 ms	2652 KB	Output is correct
19	Correct	321 ms	2792 KB	Output is correct
20	Correct	321 ms	2648 KB	Output is correct
21	Correct	330 ms	2780 KB	Output is correct
22	Correct	777 ms	5120 KB	Output is correct
23	Correct	101 ms	860 KB	Output is correct
24	Correct	313 ms	1884 KB	Output is correct
25	Correct	10 ms	348 KB	Output is correct
26	Correct	82 ms	888 KB	Output is correct
27	Correct	556 ms	860 KB	Output is correct
28	Execution timed out	1037 ms	11528 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	1070 ms	9308 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	1067 ms	11360 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #1054146

Compilation message