#include <bits/stdc++.h>
using namespace std;
#define int long long
//BIT Fenwick tree
struct fenwick{
long long bit[500011]={0} , n = 500010;
void build(){
for(int i = 0;i<=500010;i++)bit[i] = -1e13;
}
void add(int e,long long v){
while(e<=n){
bit[e]=max(bit[e],v);
e+=e&-e;
}
}
long long sum(int e){
long long res = -1e13;
while(e>=1){
res=max(res,bit[e]);
e -= e&-e;
}
return res;
}
};
fenwick s1,s2;
long long n,u,d,s;
void update(long long i,long long val){
s1.add(i,val+d*i);
s2.add(500002-i,val-u*i);
}long long get(long long i){
return max(s2.sum(500002-i)+u*i,s1.sum(i)-d*i);
}
//end BIT
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
s1.build();s2.build();
cin>>n>>u>>d>>s;
vector<pair<long long,long long>> v[500005];
for(int i = 0;i<n;i++){
long long a,b,c;
cin>>a>>b>>c;
v[a].push_back({b,c});
}
update(s,0);
for(long long i = 0;i<=500004;i++){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end());
long long cur[v[i].size()] ;
long long maxD[v[i].size()] ;
long long maxU[v[i].size()];
for(int j = 0;j<v[i].size();j++){
cur[j] = -1e13 , maxD[j] =-1e13 , maxU[j] = -1e13;
cur[j] = get(v[i][j].first)+v[i][j].second;
}
long long tempD = -1e13,tempU = -1e13;
for(int j = 0;j<v[i].size();j++){
maxD[j] = max(cur[j],tempD-d*v[i][j].first+v[i][j].second);
tempD = max(tempD,maxD[j]+d*v[i][j].first);
}
for(int j = v[i].size()-1;j>=0;j--){
maxU[j] = max(cur[j],tempU+u*v[i][j].first+v[i][j].second);
tempU = max(tempU,maxU[j]-u*v[i][j].first);
}
for(int j = 0;j<v[i].size();j++){
cur[j] = max({cur[j],maxD[j],maxU[j]});
update(v[i][j].first,cur[j]);
}
}
cout<<get(s)<<endl;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:52:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int j = 0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
salesman.cpp:57:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j = 0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
salesman.cpp:65:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j = 0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19776 KB |
Output is correct |
2 |
Correct |
10 ms |
19796 KB |
Output is correct |
3 |
Correct |
10 ms |
19876 KB |
Output is correct |
4 |
Correct |
10 ms |
19888 KB |
Output is correct |
5 |
Correct |
12 ms |
19924 KB |
Output is correct |
6 |
Correct |
19 ms |
20436 KB |
Output is correct |
7 |
Correct |
33 ms |
21332 KB |
Output is correct |
8 |
Correct |
52 ms |
22988 KB |
Output is correct |
9 |
Correct |
75 ms |
24564 KB |
Output is correct |
10 |
Correct |
128 ms |
29152 KB |
Output is correct |
11 |
Correct |
157 ms |
29264 KB |
Output is correct |
12 |
Correct |
191 ms |
32340 KB |
Output is correct |
13 |
Correct |
197 ms |
32340 KB |
Output is correct |
14 |
Correct |
299 ms |
35520 KB |
Output is correct |
15 |
Correct |
239 ms |
35520 KB |
Output is correct |
16 |
Correct |
269 ms |
35404 KB |
Output is correct |
17 |
Correct |
11 ms |
19796 KB |
Output is correct |
18 |
Correct |
10 ms |
19796 KB |
Output is correct |
19 |
Correct |
12 ms |
19924 KB |
Output is correct |
20 |
Correct |
11 ms |
19916 KB |
Output is correct |
21 |
Correct |
12 ms |
19924 KB |
Output is correct |
22 |
Correct |
14 ms |
19924 KB |
Output is correct |
23 |
Correct |
13 ms |
19924 KB |
Output is correct |
24 |
Correct |
12 ms |
20004 KB |
Output is correct |
25 |
Correct |
40 ms |
22012 KB |
Output is correct |
26 |
Correct |
71 ms |
24680 KB |
Output is correct |
27 |
Correct |
113 ms |
28252 KB |
Output is correct |
28 |
Correct |
125 ms |
28004 KB |
Output is correct |
29 |
Correct |
154 ms |
29152 KB |
Output is correct |
30 |
Correct |
181 ms |
31808 KB |
Output is correct |