#include <bits/stdc++.h>
#define Task "SALES"
using namespace std;
struct Seg_Tree{
vector<int>ST;
void reset(int n){
ST.resize(n*4+5);
fill(begin(ST),end(ST),-1e9);
}
void upd(int id,int l,int r,int i,int v){
if (l>i||r<i) return;
if (l==r){
ST[id]=max(ST[id],v);
return;
}
int mid=(l+r)/2;
upd(id*2,l,mid,i,v), upd(id*2+1,mid+1,r,i,v);
ST[id]=max(ST[id*2],ST[id*2+1]);
}
int get_max(int id,int l,int r,int L,int R){
if (l>R||L>r) {
return -1e9;
}
if (L<=l&&r<=R) return ST[id];
int mid=(l+r)/2;
return max(get_max(id*2,l,mid,L,R),get_max(id*2+1,mid+1,r,L,R));
}
}up,down;
struct rand_struct{
int L,T,M;
int best;
int cur,base;
bool operator <(const rand_struct &other ) const{
if (T!=other.T) return T<other.T;
else return L<other.L;
}
};
const int maxn=5e5+5;
int N;
rand_struct a[maxn];
int U,D,S;
int cost (int i,int j){
if (i>=j) return (i-j)*U;
else return (j-i)*D;
}
int query(int i){
int Down=down.get_max(1,1,maxn-4,a[i].L,maxn-4)+a[i].L*U+a[i].M;
int Up=up.get_max(1,1,maxn-4,1,a[i].L)-a[i].L*D+a[i].M;
return max(Up,Down);
}
void update (int i){
down.upd(1,1,maxn-4,a[i].L,a[i].best-a[i].L*U);
up.upd(1,1,maxn-4,a[i].L,a[i].best+a[i].L*D);
}
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(Task".INP","r")){
freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
}
up.reset(maxn),down.reset(maxn);
cin >>N>>U>>D>>S;
for (int i=1;i<=N;++i) cin>>a[i].T>>a[i].L>>a[i].M;
a[0].L=S, a[0].T=-1;
a[N+1].L=S, a[N+1].T=maxn-4;
sort (a,a+2+N);
update(0);
for (int i=1;i<=N;++i){
if (i==N||a[i].T!=a[i+1].T){
a[i].best=query(i);
///cerr<<a[i].best<<'\n';
update(i);
}
else{
int first=i;
while(i<=N&&a[i].T==a[first].T) ++i;
--i;
int last=i;
for (int j=first;j<=last;++j){
a[j].base=query(j);
a[j].best=a[j].base;
}
a[first].cur=a[first].base;
for (int j=first+1;j<=last;++j){
int val=a[j-1].cur-cost(a[j-1].L,a[j].L)+a[j].M;
if (val>a[j].base){
a[j].cur=val;
}
else a[j].cur=a[j].base;
if (a[j].cur>a[j].best) a[j].best=a[j].cur;
}
a[last].cur=a[last].base;
for (int j=last-1;j>=first;--j){
int val=a[j+1].cur-cost (a[j+1].L,a[j].L)+a[j].M;
if (val>a[j].base) a[j].cur=val;
else a[j].cur=a[j].base;
if (a[j].cur>a[j].best) a[j].best=a[j].cur;
}
for (int j=first;j<=last;++j) update(j);
}
}
cout <<max(0,query(N+1));
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:69:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:69:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
15992 KB |
Output is correct |
2 |
Correct |
20 ms |
15992 KB |
Output is correct |
3 |
Correct |
20 ms |
15992 KB |
Output is correct |
4 |
Correct |
22 ms |
16120 KB |
Output is correct |
5 |
Correct |
25 ms |
16248 KB |
Output is correct |
6 |
Correct |
51 ms |
16888 KB |
Output is correct |
7 |
Correct |
110 ms |
18040 KB |
Output is correct |
8 |
Correct |
187 ms |
20236 KB |
Output is correct |
9 |
Correct |
251 ms |
22008 KB |
Output is correct |
10 |
Correct |
400 ms |
27896 KB |
Output is correct |
11 |
Correct |
498 ms |
28548 KB |
Output is correct |
12 |
Correct |
665 ms |
31652 KB |
Output is correct |
13 |
Correct |
657 ms |
31976 KB |
Output is correct |
14 |
Correct |
796 ms |
36792 KB |
Output is correct |
15 |
Correct |
652 ms |
35832 KB |
Output is correct |
16 |
Correct |
816 ms |
35828 KB |
Output is correct |
17 |
Correct |
21 ms |
15996 KB |
Output is correct |
18 |
Correct |
19 ms |
15992 KB |
Output is correct |
19 |
Correct |
20 ms |
16120 KB |
Output is correct |
20 |
Correct |
22 ms |
16120 KB |
Output is correct |
21 |
Correct |
21 ms |
16120 KB |
Output is correct |
22 |
Correct |
24 ms |
16120 KB |
Output is correct |
23 |
Correct |
40 ms |
16248 KB |
Output is correct |
24 |
Correct |
25 ms |
16248 KB |
Output is correct |
25 |
Correct |
151 ms |
19832 KB |
Output is correct |
26 |
Correct |
312 ms |
23608 KB |
Output is correct |
27 |
Correct |
478 ms |
28764 KB |
Output is correct |
28 |
Correct |
633 ms |
29600 KB |
Output is correct |
29 |
Correct |
826 ms |
34424 KB |
Output is correct |
30 |
Correct |
685 ms |
35192 KB |
Output is correct |