#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
///#define ll long long
typedef pair<int,int> pii;
const int maxtree=1300000;
const int maxn=500001;
const int inf=INT_MAX-10000000;
int n,s,u,d;
int tree[maxtree],tree2[maxtree],lazy[maxtree],lazy2[maxtree];
vector<pii>vect[maxn+10];
int dist(int x,int y){
return y-x+1;
}
void build(int x,int l,int r){
if(l==r){
if(l==s)tree[x]=-l*d;
else tree[x]=-inf;
if(l==s)tree2[x]=-dist(l,maxn)*u;
else tree2[x]=-inf;
return;
}
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
tree[x]=max(tree[x*2],tree[x*2+1]);
tree2[x]=max(tree2[x*2],tree2[x*2+1]);
}
void push(int x,int tree1[],int lazy1[]){
if(lazy1[x]==0)return;
tree1[x*2]+=lazy1[x];
lazy1[x*2]+=lazy1[x];
tree1[x*2+1]+=lazy1[x];
lazy1[x*2+1]+=lazy1[x];
lazy1[x]=0;
}
void update(int x,int l,int r,int ll,int rr,int val,int tree1[],int lazy1[],int tip){
if(l>rr || r<ll)return;
if(l>=ll && r<=rr){
if(tip==0){
tree1[x]=val;
return;
}
else{
tree1[x]+=val;
lazy1[x]+=val;
return;
}
}
int mid=(l+r)/2;
push(x,tree1,lazy1);
update(x*2,l,mid,ll,rr,val,tree1,lazy1,tip);
update(x*2+1,mid+1,r,ll,rr,val,tree1,lazy1,tip);
tree1[x]=max(tree1[x*2],tree1[x*2+1]);
}
int query(int x,int l,int r,int ll,int rr,int tree1[],int lazy1[]){
if(l>rr || r<ll)return -inf;
if(l>=ll && r<=rr)return tree1[x];
int mid=(l+r)/2;
push(x,tree1,lazy1);
return max(query(x*2,l,mid,ll,rr,tree1,lazy1),query(x*2+1,mid+1,r,ll,rr,tree1,lazy1));
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d %d %d %d",&n,&u,&d,&s);
u=-u;
d=-d;
build(1,1,maxn);
for(int i=1;i<=n;i++){
int t,l,k;
scanf("%d %d %d",&t,&l,&k);
vect[t].pb({l,k});
}
for(int i=1;i<=maxn;i++){
sort(vect[i].begin(),vect[i].end());
pii niz[vect[i].size()];
int niz2[vect[i].size()];
for(int j=0;j<vect[i].size();j++){
int id=vect[i][j].ff;
niz[j].ff=query(1,1,maxn,1,id,tree,lazy)+d*id;
niz[j].ss=query(1,1,maxn,id,maxn,tree2,lazy2)+u*dist(id,maxn);
///printf(" ||| %d %d FWAVVVV\n",niz[j].ff,niz[j].ss);
}
for(int j=0;j<vect[i].size();j++){
int id=vect[i][j].ff;
int pom=query(1,1,maxn,1,id,tree,lazy);
pom=max(pom+d*id,niz[j].ss);
niz2[j]=pom+vect[i][j].ss;
update(1,1,maxn,id,id,pom-d*id,tree,lazy,0);
update(1,1,maxn,1,id,vect[i][j].ss,tree,lazy,1);
}
for(int j=vect[i].size()-1;j>=0;j--){
int id=vect[i][j].ff;
int pom=query(1,1,maxn,id,maxn,tree2,lazy2);
pom=max(pom+u*dist(id,maxn),niz[j].ff);
niz2[j]=max(niz2[j],pom+vect[i][j].ss);
///printf("%d AA\n",pom);
update(1,1,maxn,id,id,pom-u*dist(id,maxn),tree2,lazy2,0);
update(1,1,maxn,id,maxn,vect[i][j].ss,tree2,lazy2,1);
}
for(int j=0;j<vect[i].size();j++){
int id=vect[i][j].ff;
update(1,1,maxn,1,id,-vect[i][j].ss,tree,lazy,1);
update(1,1,maxn,id,maxn,-vect[i][j].ss,tree2,lazy2,1);
}
for(int j=0;j<vect[i].size();j++){
int id=vect[i][j].ff;
///printf("%d | %d %d AFSA\n",i,id,niz2[j]);
update(1,1,maxn,id,id,niz2[j]-d*id,tree,lazy,0);
update(1,1,maxn,id,id,niz2[j]-u*dist(id,maxn),tree2,lazy2,0);
}
///if(vect[i].size()>0)printf("%d %d %d REZULTAT >>>>>>>>>>>>\n",query(1,1,maxn,80,80,tree,lazy)+80*d,query(1,1,maxn,120,120,tree,lazy)+120*d,query(1,1,maxn,75,75,tree,lazy)+75*d);
///if(vect[i].size()>0)printf("%d %d %d REZULTAT >>>>>>>>>>>>\n",query(1,1,maxn,80,80,tree2,lazy2)+dist(80,maxn)*u,query(1,1,maxn,120,120,tree2,lazy2)+dist(120,maxn)*u,query(1,1,maxn,75,75,tree2,lazy2)+dist(75,maxn)*u);
}
printf("%d\n",max(query(1,1,maxn,1,s,tree,lazy)+d*s,query(1,1,maxn,s,maxn,tree2,lazy2)+u*dist(s,maxn)));
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vect[i].size();j++){
~^~~~~~~~~~~~~~~
salesman.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vect[i].size();j++){
~^~~~~~~~~~~~~~~
salesman.cpp:129:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vect[i].size();j++){
~^~~~~~~~~~~~~~~
salesman.cpp:136:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vect[i].size();j++){
~^~~~~~~~~~~~~~~
salesman.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&n,&u,&d,&s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&t,&l,&k);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
20352 KB |
Output is correct |
2 |
Correct |
21 ms |
20352 KB |
Output is correct |
3 |
Correct |
27 ms |
20608 KB |
Output is correct |
4 |
Correct |
29 ms |
20480 KB |
Output is correct |
5 |
Correct |
37 ms |
20608 KB |
Output is correct |
6 |
Correct |
113 ms |
29432 KB |
Output is correct |
7 |
Correct |
257 ms |
31032 KB |
Output is correct |
8 |
Correct |
488 ms |
33584 KB |
Output is correct |
9 |
Correct |
690 ms |
35704 KB |
Output is correct |
10 |
Correct |
1287 ms |
42816 KB |
Output is correct |
11 |
Correct |
1346 ms |
43384 KB |
Output is correct |
12 |
Correct |
1867 ms |
47224 KB |
Output is correct |
13 |
Correct |
1836 ms |
47480 KB |
Output is correct |
14 |
Correct |
2179 ms |
53240 KB |
Output is correct |
15 |
Correct |
2104 ms |
52276 KB |
Output is correct |
16 |
Correct |
2317 ms |
52492 KB |
Output is correct |
17 |
Correct |
21 ms |
20352 KB |
Output is correct |
18 |
Correct |
22 ms |
20352 KB |
Output is correct |
19 |
Correct |
24 ms |
20480 KB |
Output is correct |
20 |
Correct |
29 ms |
20480 KB |
Output is correct |
21 |
Correct |
29 ms |
20480 KB |
Output is correct |
22 |
Correct |
39 ms |
20608 KB |
Output is correct |
23 |
Correct |
37 ms |
20608 KB |
Output is correct |
24 |
Correct |
38 ms |
20608 KB |
Output is correct |
25 |
Correct |
427 ms |
30968 KB |
Output is correct |
26 |
Correct |
849 ms |
33760 KB |
Output is correct |
27 |
Correct |
1462 ms |
37452 KB |
Output is correct |
28 |
Correct |
1487 ms |
38084 KB |
Output is correct |
29 |
Correct |
2179 ms |
40048 KB |
Output is correct |
30 |
Correct |
2168 ms |
41892 KB |
Output is correct |