#include <bits/stdc++.h>
using namespace std;
int T[505050], S[505050], C[505050], K[505050];
int dp[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_K(int ca, int cb) { return K[ca] < K[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()
{
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;T[K[r]]==T[K[l]];r++);
sort(K+l, K+r, comp_K);
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]]);
}
for(i=l+1;i<r;i++){
dp[K[i]] = max(dp[K[i]], dp[K[i-1]] - d * (S[K[i]] - S[K[i-1]]));
}
for(i=r-1;i>=r;i--){
dp[K[i]] = max(dp[K[i]], dp[K[i+1]] - u * (S[K[i+1]] - S[K[i]]));
}
for(i=l;i<r;i++){
dp[K[i]] += C[K[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:88:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n",ans);
^
salesman.cpp:43: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:48: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 |
Incorrect |
81 ms |
2296 KB |
Output isn't correct |
2 |
Correct |
2 ms |
2296 KB |
Output is correct |
3 |
Correct |
4 ms |
2296 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
6 ms |
2296 KB |
Output is correct |
6 |
Correct |
33 ms |
9648 KB |
Output is correct |
7 |
Correct |
76 ms |
11244 KB |
Output is correct |
8 |
Correct |
162 ms |
13832 KB |
Output is correct |
9 |
Correct |
220 ms |
17112 KB |
Output is correct |
10 |
Correct |
448 ms |
24992 KB |
Output is correct |
11 |
Correct |
428 ms |
30372 KB |
Output is correct |
12 |
Correct |
602 ms |
35540 KB |
Output is correct |
13 |
Correct |
569 ms |
35552 KB |
Output is correct |
14 |
Correct |
744 ms |
37688 KB |
Output is correct |
15 |
Correct |
687 ms |
37688 KB |
Output is correct |
16 |
Correct |
712 ms |
37688 KB |
Output is correct |
17 |
Incorrect |
139 ms |
37688 KB |
Output isn't correct |
18 |
Incorrect |
3 ms |
37688 KB |
Output isn't correct |
19 |
Incorrect |
3 ms |
37688 KB |
Output isn't correct |
20 |
Incorrect |
4 ms |
37688 KB |
Output isn't correct |
21 |
Incorrect |
5 ms |
37688 KB |
Output isn't correct |
22 |
Incorrect |
7 ms |
37688 KB |
Output isn't correct |
23 |
Incorrect |
6 ms |
37688 KB |
Output isn't correct |
24 |
Incorrect |
6 ms |
37688 KB |
Output isn't correct |
25 |
Incorrect |
132 ms |
37688 KB |
Output isn't correct |
26 |
Incorrect |
262 ms |
37688 KB |
Output isn't correct |
27 |
Incorrect |
587 ms |
37688 KB |
Output isn't correct |
28 |
Incorrect |
560 ms |
37688 KB |
Output isn't correct |
29 |
Incorrect |
780 ms |
37688 KB |
Output isn't correct |
30 |
Incorrect |
867 ms |
37688 KB |
Output isn't correct |