#include <stdio.h>
#define N 500000
#define X 500001
#define INF 0x3f3f3f3f3f3f3f3f
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int tt[N], xx[N], yy[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = tt[ii[j]] != tt[i_] ? tt[ii[j]] - tt[i_] : xx[ii[j]] - xx[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
void update(long long *ft, int i, long long x) {
while (i <= X) {
ft[i] = max(ft[i], x);
i |= i + 1;
}
}
long long query(long long *ft, int i) {
long long x = -INF;
while (i >= 0) {
x = max(x, ft[i]);
i &= i + 1, i--;
}
return x;
}
int main() {
static long long ft1[X + 1], ft2[X + 1];
static int ii[N];
static long long dp[N], dq[N], dr[N];
int n, u, d, s, h, i, j;
scanf("%d%d%d%d", &n, &u, &d, &s);
for (i = 0; i < n; i++) {
scanf("%d%d%d", &tt[i], &xx[i], &yy[i]);
ii[i] = i;
}
sort(ii, 0, n);
for (i = 0; i <= X; i++)
ft1[i] = ft2[i] = -INF;
update(ft1, s, s * d), update(ft2, X - s, -s * u);
for (i = 0; i < n; i = j) {
int t = tt[ii[i]], x;
j = i + 1;
while (j < n && tt[ii[j]] == t)
j++;
for (h = i; h < j; h++) {
x = xx[ii[h]];
dr[h] = max(query(ft1, x) - x * d, query(ft2, X - x) + x * u);
}
for (h = i; h < j; h++) {
dp[h] = dr[h];
if (h > i)
dp[h] = max(dp[h], dp[h - 1] - (xx[ii[h]] - xx[ii[h - 1]]) * d);
dp[h] += yy[ii[h]];
}
for (h = j - 1; h >= i; h--) {
dq[h] = dr[h];
if (h + 1 < j)
dq[h] = max(dq[h], dq[h + 1] - (xx[ii[h + 1]] - xx[ii[h]]) * u);
dq[h] += yy[ii[h]];
}
for (h = i; h < j; h++)
dr[h] = max(dp[h], dq[h]);
for (h = i + 1; h < j; h++)
dr[h] = max(dr[h], dr[h - 1] - (xx[ii[h]] - xx[ii[h - 1]]) * d);
for (h = j - 2; h >= i; h--)
dr[h] = max(dr[h], dr[h + 1] - (xx[ii[h + 1]] - xx[ii[h]]) * u);
for (h = i; h < j; h++) {
x = xx[ii[h]];
update(ft1, x, dr[h] + x * d), update(ft2, X - x, dr[h] - x * u);
}
}
printf("%lld\n", max(query(ft1, s) - s * d, query(ft2, X - s) + s * u));
return 0;
}
Compilation message
salesman.c: In function 'main':
salesman.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d%d%d", &n, &u, &d, &s);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d%d", &tt[i], &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8140 KB |
Output is correct |
2 |
Correct |
4 ms |
8140 KB |
Output is correct |
3 |
Correct |
5 ms |
8140 KB |
Output is correct |
4 |
Correct |
6 ms |
8236 KB |
Output is correct |
5 |
Correct |
10 ms |
8320 KB |
Output is correct |
6 |
Correct |
20 ms |
9292 KB |
Output is correct |
7 |
Correct |
46 ms |
10952 KB |
Output is correct |
8 |
Correct |
95 ms |
13824 KB |
Output is correct |
9 |
Correct |
148 ms |
16256 KB |
Output is correct |
10 |
Correct |
275 ms |
24464 KB |
Output is correct |
11 |
Correct |
332 ms |
25172 KB |
Output is correct |
12 |
Correct |
426 ms |
29848 KB |
Output is correct |
13 |
Correct |
463 ms |
30096 KB |
Output is correct |
14 |
Correct |
542 ms |
36552 KB |
Output is correct |
15 |
Correct |
519 ms |
35656 KB |
Output is correct |
16 |
Correct |
516 ms |
35668 KB |
Output is correct |
17 |
Correct |
5 ms |
8140 KB |
Output is correct |
18 |
Correct |
4 ms |
8140 KB |
Output is correct |
19 |
Correct |
6 ms |
8140 KB |
Output is correct |
20 |
Correct |
6 ms |
8280 KB |
Output is correct |
21 |
Correct |
6 ms |
8268 KB |
Output is correct |
22 |
Correct |
7 ms |
8396 KB |
Output is correct |
23 |
Correct |
8 ms |
8396 KB |
Output is correct |
24 |
Correct |
8 ms |
8396 KB |
Output is correct |
25 |
Correct |
86 ms |
13344 KB |
Output is correct |
26 |
Correct |
200 ms |
18636 KB |
Output is correct |
27 |
Correct |
343 ms |
26276 KB |
Output is correct |
28 |
Correct |
333 ms |
27116 KB |
Output is correct |
29 |
Correct |
453 ms |
34188 KB |
Output is correct |
30 |
Correct |
462 ms |
34960 KB |
Output is correct |