#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 time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
8280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Execution timed out |
1012 ms |
11416 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
5212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
5212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
8280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
