Submission #1054100

#TimeUsernameProblemLanguageResultExecution timeMemory
1054100shiomusubi496Catfish Farm (IOI22_fish)C++17
0 / 100
1065 ms11416 KiB
#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<int> P(M), Q(M); iota(all(P), 0); iota(all(Q), 0); sort(all(P), [&](int i, int j) { return X[i] != X[j] ? X[i] < X[j] : Y[i] < Y[j]; }); sort(all(Q), [&](int i, int j) { return X[i] != X[j] ? X[i] < X[j] : Y[i] > Y[j]; }); vector<int> R(N + 1); rep (i, M) ++R[X[i] + 1]; rep (i, N) R[i + 1] += R[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 行目が max なので、 i+1 行目から LDS をする { SegmentTree<Max> seg(N + 1, -inf); seg.set(N, dp0[i]); rep2 (j, R[i + 1], M) { int k = Q[j]; if (X[k] == N - 1) break; ll t = seg.prod(Y[k] + 1, N + 1) + W[k]; seg.apply(Y[k], t); chmax(dp1[X[k] + 1], seg.all_prod()); } if (i + 1 < N) chmax(dp0[i + 2], dp0[i] + Hsm[i + 1]); } // i 行目から LIS を始める { SegmentTree<Max> seg(N + 1, -inf); seg.set(0, dp1[i]); rep2 (j, R[i], M) { int k = P[j]; if (X[k] == N - 1) break; ll t = seg.prod(0, Y[k] + 1) + W[k]; seg.apply(Y[k] + 1, t); chmax(dp0[X[k] + 1], seg.all_prod()); } } } return max(*max_element(all(dp0)), *max_element(all(dp1))); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...