#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=2000000001;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
class Segment_Tree{
private:
int n;
vl date;
public:
Segment_Tree(int n_){
n=1;
while(n<n_) n*=2;
date=vl(2*n-1,-INF);
}
void Update(int k,ll x){
k+=n-1;
date[k]=max(date[k],x);
while(k>0){
k=(k-1)/2;
date[k]=max(date[k*2+1],date[k*2+2]);
}
}
ll Query(int a,int b){
a+=n-1;b+=n-1;
ll m=-INF;
while(a<b){
if(a%2==0) m=max(m,date[a++]);
if(b%2==0) m=max(m,date[--b]);
a/=2;b/=2;
}
return m;
}
ll Open(int k){return date[k+n-1];}
};
const int M=500005;
int n,L,R,s;
vp a[M];
int main(){
scanf("%d%d%d%d",&n,&L,&R,&s);
s--;
for(int i=0;i<n;i++){
int t,x,v;
scanf("%d%d%d",&t,&x,&v);
t--,x--;
a[t].push_back({x,v});
}
Segment_Tree st1(M),st2(M);
st1.Update(s,-R*(M-s-1));
st2.Update(s,-L*s);
ll res=0;
for(int i=0;i<M;i++) if(!a[i].empty()){
sort(a[i].begin(),a[i].end());
int m=a[i].size();
vl b(m),c(m),d(m);
for(int j=0;j<m;j++){
int x=a[i][j].first;
b[j]=max(st1.Query(0,x)+R*(M-x-1),st2.Query(x,M)+L*x)+a[i][j].second;
}
ll t=b[0];
for(int j=0;j<m;j++){
if(j) t=max(t-(a[i][j].first-a[i][j-1].first)*R+a[i][j].second,b[j]);
c[j]=t;
}
t=b[m-1];
for(int j=m-1;j>=0;j--){
if(j<m-1) t=max(t-(a[i][j+1].first-a[i][j].first)*L+a[i][j].second,b[j]);
d[j]=t;
}
for(int j=0;j<m;j++){
b[j]=max(c[j],d[j]);
int x=a[i][j].first;
res=max(res,b[j]-(x<s?R*(s-x):L*(x-s)));
st1.Update(x,b[j]-R*(M-x-1));
st2.Update(x,b[j]-L*x);
}
}
printf("%lld\n",res);
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d%d%d%d",&n,&L,&R,&s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d%d%d",&t,&x,&v);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
28544 KB |
Output is correct |
2 |
Correct |
18 ms |
28544 KB |
Output is correct |
3 |
Correct |
19 ms |
28544 KB |
Output is correct |
4 |
Correct |
20 ms |
28544 KB |
Output is correct |
5 |
Correct |
22 ms |
28672 KB |
Output is correct |
6 |
Correct |
47 ms |
29184 KB |
Output is correct |
7 |
Correct |
95 ms |
30072 KB |
Output is correct |
8 |
Correct |
174 ms |
31736 KB |
Output is correct |
9 |
Correct |
266 ms |
33144 KB |
Output is correct |
10 |
Correct |
449 ms |
38136 KB |
Output is correct |
11 |
Correct |
517 ms |
38008 KB |
Output is correct |
12 |
Correct |
646 ms |
41136 KB |
Output is correct |
13 |
Correct |
651 ms |
40952 KB |
Output is correct |
14 |
Correct |
801 ms |
44156 KB |
Output is correct |
15 |
Correct |
675 ms |
44324 KB |
Output is correct |
16 |
Correct |
812 ms |
44280 KB |
Output is correct |
17 |
Correct |
18 ms |
28416 KB |
Output is correct |
18 |
Correct |
19 ms |
28672 KB |
Output is correct |
19 |
Correct |
19 ms |
28544 KB |
Output is correct |
20 |
Correct |
20 ms |
28544 KB |
Output is correct |
21 |
Correct |
20 ms |
28544 KB |
Output is correct |
22 |
Correct |
22 ms |
28544 KB |
Output is correct |
23 |
Correct |
22 ms |
28544 KB |
Output is correct |
24 |
Correct |
22 ms |
28544 KB |
Output is correct |
25 |
Correct |
119 ms |
29720 KB |
Output is correct |
26 |
Correct |
210 ms |
31368 KB |
Output is correct |
27 |
Correct |
333 ms |
33892 KB |
Output is correct |
28 |
Correct |
398 ms |
33624 KB |
Output is correct |
29 |
Correct |
512 ms |
33656 KB |
Output is correct |
30 |
Correct |
490 ms |
36132 KB |
Output is correct |