#include <bits/stdc++.h>
using namespace std;
int T[505050], S[505050], C[505050], K[505050];
int dp[505050], L[505050], R[505050];
int U[1101010], D[1101010];
int n,u,d,s,ans,sz;
bool comp_T(int ca, int cb) { return T[ca] < T[cb]; }
bool comp_S(int ca, int cb) { return S[ca] < S[cb]; }
void update(int* A, int p, int v)
{
p += sz;
A[p] = max(A[p], v);
for(p>>=1;p;p>>=1){
A[p] = max(A[p<<1], A[p<<1|1]);
}
}
int find_max(int* A, int l, int r)
{
int ret = -1e9;
l += sz, r += sz;
for(;l<r;){
if(l & 1) ret = max(ret, A[l]);
if(~r & 1) ret = max(ret, A[r]);
l = l+1 >> 1;
r = r-1 >> 1;
}
if(l == r) ret = max(ret, A[l]);
return ret;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,l,r;
scanf("%d%d%d%d",&n,&u,&d,&s);
for(sz=1;sz <= s;) sz <<= 1;
for(i=0;i<n;i++){
scanf("%d%d%d",T+i,S+i,C+i);
K[i] = i;
for(;sz <= S[i];) sz <<= 1;
}
for(i=1;i<sz+sz;i++) U[i] = D[i] = -1e9;
sort(K, K+n, comp_T);
update(D, s, d * s);
update(U, s, -u * s);
for(l=0;l<n;l=r){
for(r=l;r<n && T[K[r]]==T[K[l]];r++);
sort(K+l, K+r, comp_S);
for(i=l;i<r;i++){
dp[K[i]] = max(find_max(D, 0, S[K[i]]) - d * S[K[i]], find_max(U, S[K[i]], sz-1) + u * S[K[i]]) + C[K[i]];
}
L[l] = dp[K[l]];
for(i=l+1;i<r;i++){
L[i] = max(dp[K[i]], L[i-1] - d * (S[K[i]] - S[K[i-1]]) + C[K[i]]);
}
R[r-1] = dp[K[r-1]];
for(i=r-2;i>=l;i--){
R[i] = max(dp[K[i]], R[i+1] - u * (S[K[i+1]] - S[K[i]]) + C[K[i]]);
}
for(i=l;i<r;i++){
dp[K[i]] = max(dp[K[i]], max(L[i], R[i]));
update(D, S[K[i]], dp[K[i]] + d * S[K[i]]);
update(U, S[K[i]], dp[K[i]] - u * S[K[i]]);
}
}
for(i=0;i<n;i++){
if(S[i] > s) ans = max(ans, dp[i] - u * (S[i] - s));
else ans = max(ans, dp[i] - d * (s - S[i]));
}
printf("%lld\n",ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int find_max(int*, int, int)':
salesman.cpp:31:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l+1 >> 1;
~^~
salesman.cpp:32:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r-1 >> 1;
~^~
salesman.cpp: In function 'int main()':
salesman.cpp:92:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n",ans);
^
salesman.cpp:45:7: 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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",T+i,S+i,C+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
488 KB |
Output is correct |
3 |
Correct |
3 ms |
572 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
6 ms |
788 KB |
Output is correct |
6 |
Correct |
29 ms |
9340 KB |
Output is correct |
7 |
Correct |
66 ms |
10128 KB |
Output is correct |
8 |
Correct |
148 ms |
11628 KB |
Output is correct |
9 |
Correct |
191 ms |
12824 KB |
Output is correct |
10 |
Correct |
380 ms |
17048 KB |
Output is correct |
11 |
Correct |
412 ms |
17048 KB |
Output is correct |
12 |
Correct |
579 ms |
19708 KB |
Output is correct |
13 |
Correct |
585 ms |
19772 KB |
Output is correct |
14 |
Correct |
846 ms |
22472 KB |
Output is correct |
15 |
Correct |
690 ms |
22472 KB |
Output is correct |
16 |
Correct |
714 ms |
22556 KB |
Output is correct |
17 |
Correct |
2 ms |
22556 KB |
Output is correct |
18 |
Correct |
2 ms |
22556 KB |
Output is correct |
19 |
Correct |
2 ms |
22556 KB |
Output is correct |
20 |
Correct |
4 ms |
22556 KB |
Output is correct |
21 |
Correct |
4 ms |
22556 KB |
Output is correct |
22 |
Correct |
6 ms |
22556 KB |
Output is correct |
23 |
Correct |
5 ms |
22556 KB |
Output is correct |
24 |
Correct |
6 ms |
22556 KB |
Output is correct |
25 |
Correct |
130 ms |
22556 KB |
Output is correct |
26 |
Correct |
228 ms |
22556 KB |
Output is correct |
27 |
Correct |
410 ms |
22556 KB |
Output is correct |
28 |
Correct |
405 ms |
22556 KB |
Output is correct |
29 |
Correct |
689 ms |
22592 KB |
Output is correct |
30 |
Correct |
656 ms |
22684 KB |
Output is correct |