#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
const int MAXVAL = 5e5+10;
const ll NEGINF= -1e17;
struct SEG
{
ll tree[4*MAXVAL+10];
SEG() { for(int i=1; i<=4*MAXVAL; i++) tree[i]=NEGINF; }
void update(int node, int tl, int tr, int pos, ll val)
{
if(tr<pos || pos<tl) return;
if(tl==tr) { tree[node]=max(tree[node], val); return; }
int mid=tl+tr>>1;
update(node*2, tl, mid, pos, val);
update(node*2+1, mid+1, tr, pos, val);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
ll query(int node, int tl, int tr, int l, int r)
{
if(r<tl || tr<l) return NEGINF;
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
void update(int pos, ll val) { update(1, 1, MAXVAL, pos, val); }
ll query(int l, int r) { return query(1, 1, MAXVAL, l, r); }
};
SEG sega, segb;
struct Data
{
int T, L, M;
bool operator < (const Data &p)
{
if(T!=p.T) return T<p.T;
return L<p.L;
}
};
int N, U, D, S;
Data A[MAXN+10];
ll dpl[MAXN+10], dpr[MAXN+10];
int main()
{
int i, j;
scanf("%d%d%d%d", &N, &U, &D, &S);
for(i=1; i<=N; i++) scanf("%d%d%d", &A[i].T, &A[i].L, &A[i].M);
sort(A+1, A+N+1);
sega.update(S, -U*S);
segb.update(S, D*S);
for(i=1; i<=N; )
{
int now=A[i].T;
vector<int> V;
for(; i<=N && now==A[i].T; i++) V.push_back(i);
for(int it : V) dpl[it]=dpr[it]=max(sega.query(A[it].L, MAXVAL)+U*A[it].L, segb.query(1, A[it].L)-D*A[it].L)+A[it].M;
for(j=V.size()-2; j>=0; j--) dpl[V[j]]=max(dpl[V[j]], dpl[V[j+1]]-U*(A[V[j+1]].L-A[V[j]].L)+A[V[j]].M);
for(j=1; j<V.size(); j++) dpr[V[j]]=max(dpr[V[j]], dpr[V[j-1]]-D*(A[V[j]].L-A[V[j-1]].L)+A[V[j]].M);
for(int it : V) sega.update(A[it].L, max(dpl[it], dpr[it])-A[it].L*U), segb.update(A[it].L, max(dpl[it], dpr[it])+A[it].L*D);
}
printf("%lld", max(sega.query(S, MAXVAL)+U*S, segb.query(1, S)-D*S));
}
Compilation message
salesman.cpp: In member function 'void SEG::update(int, int, int, int, ll)':
salesman.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
salesman.cpp: In member function 'll SEG::query(int, int, int, int, int)':
salesman.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
salesman.cpp: In function 'int main()':
salesman.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=1; j<V.size(); j++) dpr[V[j]]=max(dpr[V[j]], dpr[V[j-1]]-D*(A[V[j]].L-A[V[j-1]].L)+A[V[j]].M);
~^~~~~~~~~
salesman.cpp:59: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:60:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d%d%d", &A[i].T, &A[i].L, &A[i].M);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
31616 KB |
Output is correct |
2 |
Correct |
19 ms |
31744 KB |
Output is correct |
3 |
Correct |
21 ms |
31616 KB |
Output is correct |
4 |
Correct |
21 ms |
31872 KB |
Output is correct |
5 |
Correct |
24 ms |
31872 KB |
Output is correct |
6 |
Correct |
47 ms |
32504 KB |
Output is correct |
7 |
Correct |
98 ms |
33912 KB |
Output is correct |
8 |
Correct |
177 ms |
36216 KB |
Output is correct |
9 |
Correct |
251 ms |
38136 KB |
Output is correct |
10 |
Correct |
419 ms |
44536 KB |
Output is correct |
11 |
Correct |
504 ms |
45196 KB |
Output is correct |
12 |
Correct |
648 ms |
48760 KB |
Output is correct |
13 |
Correct |
628 ms |
49016 KB |
Output is correct |
14 |
Correct |
786 ms |
54392 KB |
Output is correct |
15 |
Correct |
674 ms |
53496 KB |
Output is correct |
16 |
Correct |
834 ms |
53496 KB |
Output is correct |
17 |
Correct |
19 ms |
31616 KB |
Output is correct |
18 |
Correct |
19 ms |
31616 KB |
Output is correct |
19 |
Correct |
20 ms |
31616 KB |
Output is correct |
20 |
Correct |
21 ms |
31744 KB |
Output is correct |
21 |
Correct |
21 ms |
31744 KB |
Output is correct |
22 |
Correct |
24 ms |
31864 KB |
Output is correct |
23 |
Correct |
24 ms |
31872 KB |
Output is correct |
24 |
Correct |
24 ms |
31872 KB |
Output is correct |
25 |
Correct |
151 ms |
35832 KB |
Output is correct |
26 |
Correct |
286 ms |
40008 KB |
Output is correct |
27 |
Correct |
440 ms |
46044 KB |
Output is correct |
28 |
Correct |
508 ms |
46872 KB |
Output is correct |
29 |
Correct |
655 ms |
51960 KB |
Output is correct |
30 |
Correct |
643 ms |
53200 KB |
Output is correct |