結果
問題 | No.2859 Falling Balls |
ユーザー |
![]() |
提出日時 | 2024-07-15 12:25:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 3,000 ms |
コード長 | 1,902 bytes |
コンパイル時間 | 1,029 ms |
コンパイル使用メモリ | 87,412 KB |
最終ジャッジ日時 | 2025-02-23 15:45:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <vector>#include <iostream>#include <algorithm>using namespace std;const long long INF = 3LL << 59;class segment_tree {private:int size;vector<long long> v;public:segment_tree() : size(0), v() {}segment_tree(int n) : size(1 << (n >= 2 ? 32 - __builtin_clz(n - 1) : 0)), v(vector<long long>(size * 2, -INF)) {}void update(int pos, long long x) {pos += size;v[pos] = x;while (pos > 1) {pos /= 2;v[pos] = max(v[pos * 2 + 0], v[pos * 2 + 1]);}}long long range_max(int l, int r) {l += size;r += size;long long z = -INF;while (l != r) {if (l & 1) z = max(z, v[l++]);if (r & 1) z = max(z, v[--r]);l /= 2;r /= 2;}return z;}};struct point {long long x, y, c;bool operator<(const point& p) const {return x != p.x ? x < p.x : y < p.y;}};int main() {// step #1. inputcin.tie(nullptr);ios::sync_with_stdio(false);int N; long long K;cin >> N >> K;vector<long long> T(N), X(N), C(N);for (int i = 0; i < N; i++) {cin >> T[i];}for (int i = 0; i < N; i++) {cin >> X[i];}for (int i = 0; i < N; i++) {cin >> C[i];}// step #2. preparationvector<point> P;vector<long long> SY = { 0 };for (int i = 0; i < N; i++) {long long x = T[i] * K - X[i];long long y = T[i] * K + X[i];if (x >= 0 && y >= 0) {P.push_back(point{x, y, C[i]});SY.push_back(y);}}sort(P.begin(), P.end());sort(SY.begin(), SY.end());SY.erase(unique(SY.begin(), SY.end()), SY.end());int M = P.size();int Z = SY.size();// step #3. dynamic programmingsegment_tree seg(Z);seg.update(0, 0);for (point p : P) {int pos = lower_bound(SY.begin(), SY.end(), p.y) - SY.begin();long long x = seg.range_max(0, pos + 1);if (x != INF) {seg.update(pos, x + p.c);}}// step #4. get answer & outputlong long ans = seg.range_max(0, Z);cout << ans << endl;return 0;}