結果
問題 | No.2859 Falling Balls |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:45:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 409 ms / 3,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 4,581 ms |
コンパイル使用メモリ | 265,308 KB |
最終ジャッジ日時 | 2025-02-24 01:34:51 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001long long op(long long a,long long b){return max(a,b);}long long e(){return -Inf64;}int main(){long long N,K;cin>>N>>K;vector<long long> t(N),x(N),c(N);rep(i,N)cin>>t[i];rep(i,N)cin>>x[i];rep(i,N)cin>>c[i];vector<vector<long long>> y;vector<long long> ys;rep(i,N){y.push_back({t[i]*K+x[i],t[i]*K-x[i],c[i]});ys.push_back(t[i]*K-x[i]);}ys.push_back(0);sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());segtree<long long,op,e> seg(ys.size());{int d = distance(ys.begin(),lower_bound(ys.begin(),ys.end(),0));seg.set(d,0);}sort(y.begin(),y.end());rep(i,y.size()){if(y[i][0]<0)continue;int d = distance(ys.begin(),lower_bound(ys.begin(),ys.end(),y[i][1]));long long v = seg.prod(0,d+1) + y[i][2];seg.set(d,v);}cout<<seg.all_prod()<<endl;return 0;}