#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
constexpr int SZ = 1 << 19;
struct SegmentTree{
int T[SZ << 1];
SegmentTree(){ memset(T, 0xc0, sizeof T); }
void update(int x, int v){
x |= SZ; T[x] = max(T[x], v);
while(x >>= 1) T[x] = max(T[x], v);
}
int query(int l, int r){
l |= SZ; r |= SZ; int ret = T[0];
while(l <= r){
if(l & 1) ret = max(ret, T[l++]);
if(~r & 1) ret = max(ret, T[r--]);
l >>= 1; r >>= 1;
}
return ret;
}
};
struct Info{
int t, l, m; // time, location, money
bool operator < (const Info &info) const {
return t < info.t;
}
};
int N, U, D, S, DP[505050];
vector<PII> A[505050];
SegmentTree T_D, T_U;
void Update(int pos, int dp){
T_D.update(pos, dp + D * pos);
T_U.update(pos, dp - U * pos);
}
int Query(int pos, int money){
int dw = T_D.query(0, pos) - D * pos + money;
int up = T_U.query(pos, 505050) + U * pos + money;
return max(dw, up);
}
void SolveTime(int ti){
if(A[ti].empty()) return;
int len = A[ti].size();
vector<int> DL(len), DR(len);
for(int i=0; i<len; i++){
DL[i] = DR[i] = Query(A[ti][i].x, A[ti][i].y);
}
for(int i=len-2; i>=0; i--){
DL[i] = max(DL[i], DL[i+1] - U * (A[ti][i+1].x - A[ti][i].x) + A[ti][i].y);
}
for(int i=1; i<len; i++){
DR[i] = max(DR[i], DR[i-1] - D * (A[ti][i].x - A[ti][i-1].x) + A[ti][i].y);
}
for(int i=0; i<len; i++){
int res = max(DL[i], DR[i]);
Update(A[ti][i].x, res);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> U >> D >> S;
int sz = 0;
for(int i=1; i<=N; i++){
int t, l, m; cin >> t >> l >> m;
A[t].emplace_back(l, m);
sz = max(sz, t);
}
A[0].emplace_back(S, 0); // start
A[++sz].emplace_back(S, 0); // end
for(int i=0; i<=sz; i++) sort(A[i].begin(), A[i].end());
memset(DP, 0xc0, sizeof DP);
DP[0] = 0; Update(S, 0);
for(int i=1; i<=sz; i++) SolveTime(i);
cout << Query(S, 0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
22348 KB |
Output is correct |
2 |
Correct |
12 ms |
22260 KB |
Output is correct |
3 |
Correct |
12 ms |
22348 KB |
Output is correct |
4 |
Correct |
13 ms |
22348 KB |
Output is correct |
5 |
Correct |
15 ms |
22500 KB |
Output is correct |
6 |
Correct |
40 ms |
22852 KB |
Output is correct |
7 |
Correct |
86 ms |
23908 KB |
Output is correct |
8 |
Correct |
141 ms |
25504 KB |
Output is correct |
9 |
Correct |
221 ms |
27040 KB |
Output is correct |
10 |
Correct |
307 ms |
31812 KB |
Output is correct |
11 |
Correct |
432 ms |
31656 KB |
Output is correct |
12 |
Correct |
544 ms |
34912 KB |
Output is correct |
13 |
Correct |
527 ms |
34860 KB |
Output is correct |
14 |
Correct |
733 ms |
37992 KB |
Output is correct |
15 |
Correct |
553 ms |
37992 KB |
Output is correct |
16 |
Correct |
658 ms |
37992 KB |
Output is correct |
17 |
Correct |
11 ms |
22348 KB |
Output is correct |
18 |
Correct |
12 ms |
22348 KB |
Output is correct |
19 |
Correct |
12 ms |
22308 KB |
Output is correct |
20 |
Correct |
13 ms |
22276 KB |
Output is correct |
21 |
Correct |
13 ms |
22348 KB |
Output is correct |
22 |
Correct |
16 ms |
22328 KB |
Output is correct |
23 |
Correct |
15 ms |
22348 KB |
Output is correct |
24 |
Correct |
16 ms |
22448 KB |
Output is correct |
25 |
Correct |
89 ms |
23348 KB |
Output is correct |
26 |
Correct |
159 ms |
24604 KB |
Output is correct |
27 |
Correct |
287 ms |
26308 KB |
Output is correct |
28 |
Correct |
285 ms |
26552 KB |
Output is correct |
29 |
Correct |
358 ms |
27216 KB |
Output is correct |
30 |
Correct |
400 ms |
28036 KB |
Output is correct |