結果

問題 No.2859 Falling Balls
ユーザー square1001
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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. input
cin.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. preparation
vector<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 programming
segment_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 & output
long long ans = seg.range_max(0, Z);
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0