#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) begin(x), end(x)
//#define endl '\n'
struct node {
int l, r;
node *lft, *rht;
int lmax, rmax;
node (int tl, int tr): l(tl), r(tr), lmax(INT_MIN/2), rmax(INT_MIN/2) {
lft=rht=NULL;
/*if (l+1==r) {
lft=rht=NULL;
}
else {
lft=new node(l,(l+r)/2);
rht=new node((l+r)/2,r);
}*/
}
void clean() {
if (lft) {
return;
}
if (l+1!=r) {
lft=new node(l,(l+r)/2);
rht=new node((l+r)/2,r);
}
}
};
node *root;
int n,u,d,s;
int t,loc,m;
map<int,vector<pair<int,int>>> mp;
void update(node *x, int p, int v) {
if (x->r<=p||p<x->l) {
return;
}
if (x->l+1==x->r) {
x->lmax=max(x->lmax,v+x->l*d);
x->rmax=max(x->rmax,v-x->l*u);
return;
}
x->clean();
update(x->lft,p,v);
update(x->rht,p,v);
x->lmax=max(x->lft->lmax,x->rht->lmax);
x->rmax=max(x->lft->rmax,x->rht->rmax);
}
int qry(node *x, int l, int r, bool tmp) {
if (r<=x->l||x->r<=l) {
return INT_MIN/2;
}
if (l<=x->l&&x->r<=r) {
return tmp?x->rmax:x->lmax;
}
x->clean();
return max(qry(x->lft,l,r,tmp),qry(x->rht,l,r,tmp));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin>>n>>u>>d>>s;
root=new node(0,500069);
update(root,s,0);
for (int i = 0; i < n; i++) {
cin>>t>>loc>>m;
mp[t].push_back({loc,m});
}
for (auto &tmp : mp) {
sort(all(tmp.s));
vector<pair<int,int>> vctr;
for (auto i : tmp.s) {
tie(loc,m)=i;
int tmp=qry(root,0,loc,0)-loc*d;
tmp=max(tmp,qry(root,loc,500069,1)+loc*u);
vctr.push_back({loc,tmp+m});
}
int l=vctr.size();
vector<int> a(l),b(l);
a[0]=vctr[0].s;
for (int i = 1; i < l; i++) {
a[i]=max(vctr[i].s,a[i-1]-(vctr[i].f-vctr[i-1].f)*d+tmp.s[i].s);
}
b[l-1]=vctr[l-1].s;
for (int i = l-2; ~i; i--) {
b[i]=max(vctr[i].s,b[i+1]-(vctr[i+1].f-vctr[i].f)*u+tmp.s[i].s);
}
for (int i = 0; i < l; i++) {
update(root,vctr[i].f,max(a[i],b[i]));
}
}
int tmp=qry(root,0,s,0)-s*d;
tmp=max(tmp,qry(root,s,500069,1)+s*u);
cout<<tmp<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
724 KB |
Output is correct |
5 |
Correct |
7 ms |
1280 KB |
Output is correct |
6 |
Correct |
36 ms |
10132 KB |
Output is correct |
7 |
Correct |
108 ms |
22456 KB |
Output is correct |
8 |
Correct |
221 ms |
35664 KB |
Output is correct |
9 |
Correct |
329 ms |
34992 KB |
Output is correct |
10 |
Runtime error |
474 ms |
65536 KB |
Execution killed with signal 9 |
11 |
Runtime error |
509 ms |
65536 KB |
Execution killed with signal 9 |
12 |
Runtime error |
482 ms |
65536 KB |
Execution killed with signal 9 |
13 |
Runtime error |
543 ms |
65536 KB |
Execution killed with signal 9 |
14 |
Runtime error |
639 ms |
65536 KB |
Execution killed with signal 9 |
15 |
Runtime error |
619 ms |
65536 KB |
Execution killed with signal 9 |
16 |
Runtime error |
584 ms |
65536 KB |
Execution killed with signal 9 |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
356 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
22 |
Correct |
5 ms |
852 KB |
Output is correct |
23 |
Correct |
5 ms |
776 KB |
Output is correct |
24 |
Correct |
5 ms |
952 KB |
Output is correct |
25 |
Correct |
164 ms |
26496 KB |
Output is correct |
26 |
Correct |
270 ms |
37036 KB |
Output is correct |
27 |
Correct |
443 ms |
46820 KB |
Output is correct |
28 |
Correct |
549 ms |
38788 KB |
Output is correct |
29 |
Correct |
726 ms |
51676 KB |
Output is correct |
30 |
Correct |
694 ms |
52576 KB |
Output is correct |