#include <iostream>
#include <algorithm>
#define f first
#define s second
using namespace std;
const long long n = 5e5+1;
long long m, u, d, st, node[2][2000010], dp[2][500010], lst;
pair<long long,pair<long long,long long>> event[2][500010];
void build(int i, int id, int x, int y) {
if (x == y) {
if (x == st) {
if (i == 0) node[i][id] = -u*st;
else node[i][id] = -d*(n-st);
} else node[i][id] = -1e18;
return;
}
int mid = (x+y)/2;
build(i,id*2,x,mid);
build(i,id*2+1,mid+1,y);
node[i][id] = max(node[i][id*2],node[i][id*2+1]);
}
long long query(int i, int id, int x, int y, int l, int r) {
if ((l <= x) && (y <= r)) return node[i][id];
if ((y < l) || (r < x)) return -1e18;
int mid = (x+y)/2;
return max(query(i,id*2,x,mid,l,r),query(i,id*2+1,mid+1,y,l,r));
}
void update(int i, int id, int x, int y, int pos, long long val) {
if (x == y) {
if (i == 0) node[i][id] = max(node[i][id],val-u*pos);
else node[i][id] = max(node[i][id],val-d*(n-pos));
return;
}
int mid = (x+y)/2;
if (pos <= mid) update(i,id*2,x,mid,pos,val);
else update(i,id*2+1,mid+1,y,pos,val);
node[i][id] = max(node[i][id*2],node[i][id*2+1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> m >> u >> d >> st;
for (int i = 1; i <= m; i++) {
cin >> event[0][i].f >> event[0][i].s.f >> event[0][i].s.s;
event[1][i] = event[0][i];
event[1][i].s.f = -event[1][i].s.f;
}
sort(event[0]+1,event[0]+m+1);
sort(event[1]+1,event[1]+m+1);
for (int i = 1; i <= m; i++) event[1][i].s.f = -event[1][i].s.f;
build(0,1,1,n);
build(1,1,1,n);
for (int i = 1; i <= m; i++) {
if (event[0][i].f != event[0][i-1].f) {
if (lst) {
for (int k = 0; k <= 1; k++) {
for (int j = lst; j < i; j++) {
update(0,1,1,n,event[k][j].s.f,dp[k][j]);
update(1,1,1,n,event[k][j].s.f,dp[k][j]);
}
}
}
long long pos = event[0][i].s.f, val = event[0][i].s.s;
dp[0][i] = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
pos = event[1][i].s.f, val = event[1][i].s.s;
dp[1][i] = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
lst = i;
} else {
long long pos = event[0][i].s.f, val = event[0][i].s.s;
long long pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
dp[0][i] = max(pro,dp[0][i-1]+val-d*(pos-event[0][i-1].s.f));
pos = event[1][i].s.f, val = event[1][i].s.s;
pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
dp[1][i] = max(pro,dp[1][i-1]+val-u*(event[1][i-1].s.f-pos));
}
}
for (int k = 0; k <= 1; k++) {
for (int j = lst; j <= n; j++) {
update(0,1,1,n,event[k][j].s.f,dp[k][j]);
update(1,1,1,n,event[k][j].s.f,dp[k][j]);
}
}
long long pos = st, val = 0;
long long pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
update(0,1,1,n,pos,pro);
update(1,1,1,n,pos,pro);
cout << query(0,1,1,n,pos,pos)+(u*pos) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
204 ms |
16904 KB |
Output is correct |
| 3 |
Correct |
203 ms |
16840 KB |
Output is correct |
| 4 |
Correct |
205 ms |
16948 KB |
Output is correct |
| 5 |
Correct |
218 ms |
17160 KB |
Output is correct |
| 6 |
Correct |
244 ms |
18416 KB |
Output is correct |
| 7 |
Correct |
291 ms |
20824 KB |
Output is correct |
| 8 |
Correct |
383 ms |
24856 KB |
Output is correct |
| 9 |
Correct |
503 ms |
28540 KB |
Output is correct |
| 10 |
Correct |
691 ms |
40252 KB |
Output is correct |
| 11 |
Correct |
766 ms |
40948 KB |
Output is correct |
| 12 |
Correct |
963 ms |
47828 KB |
Output is correct |
| 13 |
Correct |
893 ms |
48224 KB |
Output is correct |
| 14 |
Correct |
1103 ms |
56956 KB |
Output is correct |
| 15 |
Correct |
924 ms |
56064 KB |
Output is correct |
| 16 |
Correct |
1201 ms |
56072 KB |
Output is correct |
| 17 |
Correct |
203 ms |
16780 KB |
Output is correct |
| 18 |
Correct |
199 ms |
16812 KB |
Output is correct |
| 19 |
Correct |
207 ms |
16868 KB |
Output is correct |
| 20 |
Correct |
214 ms |
16968 KB |
Output is correct |
| 21 |
Correct |
216 ms |
16992 KB |
Output is correct |
| 22 |
Correct |
217 ms |
17300 KB |
Output is correct |
| 23 |
Correct |
235 ms |
17100 KB |
Output is correct |
| 24 |
Correct |
209 ms |
17180 KB |
Output is correct |
| 25 |
Correct |
387 ms |
24476 KB |
Output is correct |
| 26 |
Correct |
530 ms |
32092 KB |
Output is correct |
| 27 |
Correct |
784 ms |
43176 KB |
Output is correct |
| 28 |
Correct |
797 ms |
44040 KB |
Output is correct |
| 29 |
Correct |
1029 ms |
54588 KB |
Output is correct |
| 30 |
Correct |
1008 ms |
55532 KB |
Output is correct |
