#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=(int)5e5+1;
const int P=6e5;
const long long INF=(long long)1e18+7;
struct Tree
{
int pot;
long long t[2*P+10];
void init(int _pot)
{
pot=_pot;
for(int i=1;i<=2*pot;i++)
t[i]=-INF;
return;
}
void upd(int x,long long c)
{
for(x+=pot-1;x>0;x/=2)
t[x]=max(t[x],c);
return;
}
long long read(int l,int r)
{
long long ans=-INF;
for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
{
if(l%2==1)
ans=max(ans,t[l++]);
if(r%2==0)
ans=max(ans,t[r--]);
}
return ans;
}
};
vector<pair<int,int>> fair[N+10];
Tree up,down;
long long read(int x,int u,int d)
{
return max(up.read(x,N)+x*u,down.read(1,x)-x*d);
}
void upd(int x,long long c,int u,int d)
{
up.upd(x,c-x*u);
down.upd(x,c+x*d);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,d,u,s;
cin>>n>>u>>d>>s;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
fair[a].emplace_back(b,c);
}
int pot;
for(pot=1;pot<N;pot*=2);
up.init(pot);
down.init(pot);
upd(s,0,u,d);
for(int i=1;i<=N;i++)
{
if(fair[i].empty())
continue;
sort(fair[i].begin(),fair[i].end());
vector<long long> w(fair[i].size(),-INF);
long long tmp=-INF;
for(size_t j=0;j<fair[i].size();j++)
{
long long xd=read(fair[i][j].fi,u,d)+fair[i][j].se;
if(j>0)
xd=max(xd,tmp-d*(fair[i][j].fi-fair[i][j-1].fi)+fair[i][j].se);
tmp=xd;
w[j]=xd;
}
tmp=-INF;
for(int j=fair[i].size()-1;j>=0;j--)
{
long long xd=read(fair[i][j].fi,u,d)+fair[i][j].se;
if(j<fair[i].size()-1)
xd=max(xd,tmp-u*(fair[i][j+1].fi-fair[i][j].fi)+fair[i][j].se);
tmp=xd;
w[j]=max(w[j],xd);
}
//cerr<<i<<" "<<fair[i][0].fi<<" "<<w[0]<<"\n";
for(size_t j=0;j<fair[i].size();j++)
upd(fair[i][j].fi,w[j],u,d);
}
cout<<read(s,u,d)<<"\n";
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:87:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if(j<fair[i].size()-1)
| ~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
28364 KB |
Output is correct |
2 |
Correct |
18 ms |
28416 KB |
Output is correct |
3 |
Correct |
17 ms |
28388 KB |
Output is correct |
4 |
Correct |
19 ms |
28548 KB |
Output is correct |
5 |
Correct |
24 ms |
28532 KB |
Output is correct |
6 |
Correct |
45 ms |
29096 KB |
Output is correct |
7 |
Correct |
95 ms |
30032 KB |
Output is correct |
8 |
Correct |
174 ms |
31480 KB |
Output is correct |
9 |
Correct |
243 ms |
33280 KB |
Output is correct |
10 |
Correct |
418 ms |
37860 KB |
Output is correct |
11 |
Correct |
486 ms |
37972 KB |
Output is correct |
12 |
Correct |
632 ms |
41028 KB |
Output is correct |
13 |
Correct |
642 ms |
41120 KB |
Output is correct |
14 |
Correct |
790 ms |
44120 KB |
Output is correct |
15 |
Correct |
680 ms |
44116 KB |
Output is correct |
16 |
Correct |
786 ms |
44148 KB |
Output is correct |
17 |
Correct |
19 ms |
28364 KB |
Output is correct |
18 |
Correct |
19 ms |
28496 KB |
Output is correct |
19 |
Correct |
19 ms |
28460 KB |
Output is correct |
20 |
Correct |
20 ms |
28408 KB |
Output is correct |
21 |
Correct |
21 ms |
28528 KB |
Output is correct |
22 |
Correct |
21 ms |
28492 KB |
Output is correct |
23 |
Correct |
21 ms |
28576 KB |
Output is correct |
24 |
Correct |
22 ms |
28496 KB |
Output is correct |
25 |
Correct |
133 ms |
29468 KB |
Output is correct |
26 |
Correct |
246 ms |
30868 KB |
Output is correct |
27 |
Correct |
370 ms |
32524 KB |
Output is correct |
28 |
Correct |
431 ms |
32660 KB |
Output is correct |
29 |
Correct |
581 ms |
33476 KB |
Output is correct |
30 |
Correct |
545 ms |
34204 KB |
Output is correct |