//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n,uu,dd,stt;
llo ind[500001];
llo tree[2][500001*4];
vector<pair<pair<llo,llo>,pair<llo,llo>>> ss;
vector<pair<pair<llo,llo>,pair<llo,llo>>> tt;
void build(llo no,llo l,llo r,llo cot){
if(l==r){
tree[cot][no]=-(llo)1e9;
}
else{
llo mid=(l+r)/2;
build(no*2+1,l,mid,cot);
build(no*2+2,mid+1,r,cot);
tree[cot][no]=max(tree[cot][no*2+1],tree[cot][no*2+2]);
}
}
void update(llo no,llo l,llo r,llo i,llo val,llo cot){
if(l==r){
//cout<<i<<"<<"<<val<<"<<"<<cot<<endl;
tree[cot][no]=val;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,val,cot);
}
else{
update(no*2+2,mid+1,r,i,val,cot);
}
tree[cot][no]=max(tree[cot][no*2+1],tree[cot][no*2+2]);
}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo cot){
if(bb<l or aa>r){
return -1e9;
}
if(aa<=l and r<=bb){
//cout<<cot<<"<<<<<<<<<<<<<<"<<endl;
//cout<<l<<"<<"<<r<<",,"<<tree[cot][no]<<endl;
return tree[cot][no];
}
else{
llo mid=(l+r)/2;
return max(query(no*2+1,l,mid,aa,bb,cot),query(no*2+2,mid+1,r,aa,bb,cot));
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>uu>>dd>>stt;
for(llo i=0;i<n;i++){
llo aa,bb,cc;
cin>>aa>>bb>>cc;
ss.pb({{aa,bb},{cc,i}});
tt.pb({{bb,aa},{cc,i}});
}
sort(ss.begin(),ss.end());
sort(tt.begin(),tt.end());
for(llo j=0;j<n;j++){
ind[tt[j].b.b]=j;
}
llo cur=0;
build(0,0,n-1,0);
build(0,0,n-1,1);
llo ans=0;
while(cur<n){
llo cur2=cur;
while(cur<n){
if(ss[cur].a.a==ss[cur2].a.a){
cur++;
}
else{
break;
}
}
vector<llo> kk;
vector<llo> dis;
for(llo i=cur2;i<cur;i++){
llo val=0;
if(ss[i].a.b<stt){
val+=(stt-ss[i].a.b)*uu;
}
else{
val+=(ss[i].a.b-stt)*dd;
}
val=-val;
//cout<<query(0,0,n-1,ind[ss[i].b.b],n-1,0)<<endl;
val=max(val,query(0,0,n-1,ind[ss[i].b.b],n-1,0)+uu*ss[i].a.b);
val=max(val,query(0,0,n-1,0,ind[ss[i].b.b],1)-dd*ss[i].a.b);
val+=ss[i].b.a;
dis.pb(val);
}
llo cur3=0;
vector<llo> dis2;
for(auto j:dis){
dis2.pb(j);
}
vector<llo> mm;
llo cot=0;
llo mi=0;
for(int i=cur-1;i>=cur2;i--){
mi=min(mi,cot);
mm.pb(cot-mi);
if(i>cur2){
cot+=-(dd+uu)*(ss[i].a.b-ss[i-1].a.b);
cot+=ss[i].b.a;
}
}
reverse(mm.begin(),mm.end());
cot=-(llo)1e18;
mi=0;
for(int i=cur-1;i>=cur2;i--){
//mi=min(mi,cot);
if(i<cur-1){
cot-=uu*(ss[i+1].a.b-ss[i].a.b);
cot+=ss[i].b.a;
// cot=max(cot,mm[i-cur2]);
}
cot=max(cot,(llo)mm[i-cur2]+dis[i-cur2]);
dis2[i-cur2]=max(dis2[i-cur2],cot-mi);
}
vector<llo> nn;
cot=0;
mi=0;
for(int i=cur2;i<cur;i++){
mi=min(mi,cot);
nn.pb(cot-mi);
if(i+1<cur){
cot+=-(dd+uu)*(ss[i+1].a.b-ss[i].a.b);
cot+=ss[i].b.a;
}
}
cot=-(llo)1e18;
for(int i=cur2;i<cur;i++){
if(i>cur2){
cot-=dd*(ss[i].a.b-ss[i-1].a.b);
cot+=ss[i].b.a;
}
cot=max(cot,nn[i-cur2]+dis[i-cur2]);
dis2[i-cur2]=max(dis2[i-cur2],cot);
}
for(int i=0;i<dis.size();i++){
dis[i]=dis2[i];
}
/*vector<llo> mm;
vector<llo> nn;
llo cp=0;
llo mi=(llo)1e18;
llo cur3=0;
for(llo i=cur2;i<cur;i++){
mi=min(mi,cp);
mm.pb(dis[cur3]+cp-mi+ss[i].a.b*dd);
//nn.pb(dis[cur3]-ss[i].a.b*uu);
cur3++;
cp+=ss[i].b.a;
if(i+1<cur){
cp+=-(ss[i+1].a.b-ss[i].a.b)*(dd+uu);
}
}
mi=(llo)1e18;
cp=0;
for(llo i=cur-1;i>=cur2;i--){
cur3--;
mi=min(mi,cp);
nn.pb(dis[cur3]+cp-mi-ss[i].a.b*uu);
cp+=ss[i].b.a;
if(cur3!=0){
cp+=-(ss[i].a.b-ss[i-1].a.b)*(dd+uu);
}
}
reverse(nn.begin(),nn.end());
cur3=0;
llo ma=mm[0];
llo su=0;
for(auto j:dis){
su+=j;
}
vector<llo> dis2;
for(auto j:dis){
dis2.pb(j);
}
llo sot=su;
// cout<<su<<endl;
for(llo i=cur2;i<cur;i++){
su-=dis2[cur3];
ma=max(ma,mm[cur3]+su);
dis[cur3]=max(dis[cur3],ma-su-ss[i].a.b*dd);
cur3++;
}
ma=nn.back();
su=sot;
for(llo i=cur-1;i>=cur2;i--){
cur3--;
su-=dis2[cur3];
// cout<<(ma-su+ss[i].a.b*uu)<<endl;
//cout<<ma<<"<"<<su<<"<"<<ss[i].a.b<<"<"<<uu<<endl;
ma=max(ma,nn[cur3]+su);
dis[cur3]=max(dis[cur3],ma-su+ss[i].a.b*uu);
}*/
/*for(auto j:dis){
cout<<j<<",,";
}
cout<<endl;
for(auto j:mm){
cout<<j<<",,";
}
cout<<endl;*/
/*for(auto j:dis){
cout<<j<<",,";
}
cout<<endl;
*/
cur3=0;
for(llo i=cur2;i<cur;i++){
llo val=0;
if(ss[i].a.b<stt){
val+=(stt-ss[i].a.b)*dd;
}
else{
val+=(ss[i].a.b-stt)*uu;
}
val=-val;
val+=dis[cur3];
// cout<<ss[i].b.b<<":"<<dis[cur3]<<"::"<<val<<":"<<ind[ss[i].b.b]<<endl;
ans=max(ans,val);
//if(ss[i].b.b!=3){
update(0,0,n-1,ind[ss[i].b.b],dis[cur3]-ss[i].a.b*uu,0);
update(0,0,n-1,ind[ss[i].b.b],dis[cur3]+ss[i].a.b*dd,1);
//}
cur3++;
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:159:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i=0;i<dis.size();i++){
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1128 KB |
Output is correct |
| 6 |
Correct |
30 ms |
3032 KB |
Output is correct |
| 7 |
Correct |
87 ms |
6096 KB |
Output is correct |
| 8 |
Correct |
193 ms |
11716 KB |
Output is correct |
| 9 |
Correct |
306 ms |
19552 KB |
Output is correct |
| 10 |
Correct |
582 ms |
38276 KB |
Output is correct |
| 11 |
Correct |
690 ms |
38348 KB |
Output is correct |
| 12 |
Correct |
936 ms |
45188 KB |
Output is correct |
| 13 |
Correct |
939 ms |
45316 KB |
Output is correct |
| 14 |
Correct |
1183 ms |
52228 KB |
Output is correct |
| 15 |
Correct |
970 ms |
52332 KB |
Output is correct |
| 16 |
Correct |
1191 ms |
52364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
492 KB |
Output is correct |
| 20 |
Correct |
3 ms |
748 KB |
Output is correct |
| 21 |
Correct |
3 ms |
748 KB |
Output is correct |
| 22 |
Correct |
7 ms |
1128 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1128 KB |
Output is correct |
| 24 |
Correct |
7 ms |
1128 KB |
Output is correct |
| 25 |
Correct |
164 ms |
11716 KB |
Output is correct |
| 26 |
Correct |
375 ms |
23980 KB |
Output is correct |
| 27 |
Correct |
690 ms |
44932 KB |
Output is correct |
| 28 |
Correct |
770 ms |
43268 KB |
Output is correct |
| 29 |
Correct |
1081 ms |
52380 KB |
Output is correct |
| 30 |
Correct |
1026 ms |
55812 KB |
Output is correct |
