#include<bits/stdc++.h>
#define Loc first
#define Prof second
using namespace std;
const int N = 5e5 + 2 , INF = 2e9;
int n , U , D , S;
vector<pair<int , int> > fairs[N];
struct SegTree{
int T[4 * N];
void init(){
fill(T , T + 4 * N , -INF);
}
void update(int l , int r , int idx , int v , int pos){
if(idx < l || r < idx) return;
if(l == r){
T[pos] = max(T[pos] , v);
return;
}
int mid = (l + r) >> 1;
update(l , mid , idx , v , pos * 2);
update(mid + 1 , r , idx , v , pos * 2 + 1);
T[pos] = max(T[pos * 2] , T[pos * 2 + 1]);
return;
}
int query(int l , int r , int L , int R , int pos){
if(r < L || R < l) return -INF;
if(L <= l && r <= R) {
return T[pos];
}
int mid = (l + r) >> 1;
int p1 = query(l , mid , L , R , pos * 2);
int p2 = query(mid + 1 , r , L , R , pos * 2 + 1);
return max(p1 , p2);
}
}Up , Down;
void upd(int loc , int best_profit){
Up.update(1 , N - 1, loc , best_profit - U * loc , 1);
Down.update(1 , N - 1, loc , best_profit + D * loc , 1);
}
int get(int loc){
return max(Up.query(1 , N - 1, loc + 1 , N - 1 , 1) + U * loc , Down.query(1 , N - 1, 1 , loc - 1 , 1) - D * loc);
}
void solve(vector<pair<int , int> > &v){
if(!v.size()) return;
if(v.size() >= 2) {
sort(v.begin() , v.end());
}
vector<int> Us(v.size());
vector<int> Ds(v.size());
for(int i = 0; i < v.size(); ++i){
Us[i] = Ds[i] = get(v[i].Loc);
}
for(int i = 0; i < v.size(); ++i){
if(!i){Ds[i] += v[i].Prof; continue;}
Ds[i] = max(Ds[i] , Ds[i - 1] - D * (v[i].Loc - v[i - 1].Loc));
Ds[i] += v[i].Prof;
}
for(int i = v.size() - 1; i >= 0; --i){
if(i == v.size() - 1) {Us[i] += v[i].Prof; continue;}
Us[i] = max(Us[i] , Us[i + 1] - U * (v[i + 1].Loc - v[i].Loc));
Us[i] += v[i].Prof;
}
for(int i = 0; i < v.size(); ++i){
upd(v[i].Loc , max(Us[i] , Ds[i]));
}
}
int main (){
ios_base::sync_with_stdio(false);
//cin.tie(0);
scanf("%d%d%d%d" , &n , &U , &D , &S);
for(int i = 0; i < n; ++i){
int d , l , pr;
scanf("%d%d%d" , &d , &l , &pr);
fairs[d].emplace_back(l , pr);
}
Up.init(); Down.init();
upd(S , 0);
for(int i = 1; i <= 500001; ++i){
solve(fairs[i]);
}
printf("%d" , max(0 , get(S)));
return 0;
}
Compilation message
salesman.cpp: In function 'void solve(std::vector<std::pair<int, int> >&)':
salesman.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); ++i){
~~^~~~~~~~~~
salesman.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); ++i){
~~^~~~~~~~~~
salesman.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == v.size() - 1) {Us[i] += v[i].Prof; continue;}
~~^~~~~~~~~~~~~~~
salesman.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); ++i){
~~^~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:78: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:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d" , &d , &l , &pr);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
27772 KB |
Output is correct |
2 |
Correct |
29 ms |
27768 KB |
Output is correct |
3 |
Correct |
29 ms |
27768 KB |
Output is correct |
4 |
Correct |
32 ms |
27896 KB |
Output is correct |
5 |
Correct |
33 ms |
27912 KB |
Output is correct |
6 |
Correct |
65 ms |
28792 KB |
Output is correct |
7 |
Correct |
125 ms |
30220 KB |
Output is correct |
8 |
Correct |
217 ms |
31812 KB |
Output is correct |
9 |
Correct |
310 ms |
33468 KB |
Output is correct |
10 |
Correct |
557 ms |
38084 KB |
Output is correct |
11 |
Correct |
608 ms |
38332 KB |
Output is correct |
12 |
Correct |
775 ms |
41200 KB |
Output is correct |
13 |
Correct |
771 ms |
40952 KB |
Output is correct |
14 |
Correct |
955 ms |
44908 KB |
Output is correct |
15 |
Correct |
871 ms |
44716 KB |
Output is correct |
16 |
Correct |
970 ms |
44772 KB |
Output is correct |
17 |
Correct |
29 ms |
27768 KB |
Output is correct |
18 |
Correct |
29 ms |
27876 KB |
Output is correct |
19 |
Correct |
29 ms |
27784 KB |
Output is correct |
20 |
Correct |
31 ms |
27768 KB |
Output is correct |
21 |
Correct |
31 ms |
27816 KB |
Output is correct |
22 |
Correct |
34 ms |
27768 KB |
Output is correct |
23 |
Correct |
37 ms |
27896 KB |
Output is correct |
24 |
Correct |
33 ms |
27900 KB |
Output is correct |
25 |
Correct |
145 ms |
29776 KB |
Output is correct |
26 |
Correct |
258 ms |
30956 KB |
Output is correct |
27 |
Correct |
414 ms |
32572 KB |
Output is correct |
28 |
Correct |
495 ms |
32708 KB |
Output is correct |
29 |
Correct |
580 ms |
34424 KB |
Output is correct |
30 |
Correct |
600 ms |
34780 KB |
Output is correct |