#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const int MAXX = 5e5 + 1;
const llong inf = 1e16;
int n, u, d, s;
struct sale {
int t, x, m;
void scan() {
scanf("%d%d%d", &t, &x, &m);
}
bool operator<(const sale &p) const {
if (t == p.t) return x < p.x;
return t < p.t;
}
} arr[MAXX];
llong dpl[MAXX], dpr[MAXX], dp[MAXX];
llong segd[1 << 20];
llong segu[1 << 20];
void update(llong seg[], int i, int s, int e, int x, llong v) {
if (s == e) {
seg[i] = v;
return;
}
int m = (s + e) / 2;
if (x <= m) update(seg, i << 1, s, m, x, v);
else update(seg, i << 1 | 1, m + 1, e, x, v);
seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
llong query(llong seg[], int i, int s, int e, int x, int y) {
if (e < x || y < s) return -inf;
if (x <= s && e <= y) return seg[i];
int m = (s + e) / 2;
return max(query(seg, i << 1, s, m, x, y)
, query(seg, i << 1 | 1, m + 1, e, x, y));
}
int main() {
for (int i = 0; i < (1 << 20); ++i) segd[i] = segu[i] = -inf;
scanf("%d%d%d%d", &n, &u, &d, &s);
update(segu, 1, 1, MAXX, s, -u * s);
update(segd, 1, 1, MAXX, s, d * s);
for (int i = 0; i < n; ++i) {
arr[i].scan();
}
arr[n] = { MAXX + 1, s, 0 };
sort(arr, arr + n);
llong v;
for (int st = 0, ed = 0; st <= n; st = ed) {
while (ed <= n && arr[st].t == arr[ed].t) ++ed;
int x, pr, m;
for (int i = st; i < ed; ++i) {
x = arr[i].x;
m = arr[i].m;
dp[i] = max(query(segu, 1, 1, MAXX, x, MAXX) + u * x + m
, query(segd, 1, 1, MAXX, 1, x) - d * x + m);
dpr[i] = dp[i];
if (st < i) dpr[i] = max(dpr[i], dpr[i - 1] - d * (x - pr) + m);
pr = arr[i].x;
}
for (int i = ed; i-- > st; ) {
x = arr[i].x;
m = arr[i].m;
dpl[i] = dp[i];
if (i + 1 < ed)
dpl[i] = max(dpl[i], dpl[i + 1] - u * (pr - x) + m);
pr = arr[i].x;
}
for (int i = st; i < ed; ++i) {
x = arr[i].x;
m = arr[i].m;
v = max(dpl[i], dpr[i]);
update(segu, 1, 1, MAXX, x, v - u * x);
update(segd, 1, 1, MAXX, x, v + d * x);
}
}
printf("%lld\n", v);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
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: In member function 'void sale::scan()':
salesman.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &t, &x, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:78:66: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (st < i) dpr[i] = max(dpr[i], dpr[i - 1] - d * (x - pr) + m);
~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
16760 KB |
Output is correct |
2 |
Correct |
16 ms |
16868 KB |
Output is correct |
3 |
Correct |
16 ms |
16952 KB |
Output is correct |
4 |
Correct |
16 ms |
16952 KB |
Output is correct |
5 |
Correct |
20 ms |
17072 KB |
Output is correct |
6 |
Correct |
47 ms |
17576 KB |
Output is correct |
7 |
Correct |
113 ms |
18720 KB |
Output is correct |
8 |
Correct |
218 ms |
20648 KB |
Output is correct |
9 |
Correct |
282 ms |
22432 KB |
Output is correct |
10 |
Correct |
488 ms |
27604 KB |
Output is correct |
11 |
Correct |
565 ms |
27740 KB |
Output is correct |
12 |
Correct |
749 ms |
31028 KB |
Output is correct |
13 |
Correct |
843 ms |
31204 KB |
Output is correct |
14 |
Correct |
920 ms |
34540 KB |
Output is correct |
15 |
Correct |
786 ms |
34796 KB |
Output is correct |
16 |
Correct |
996 ms |
34796 KB |
Output is correct |
17 |
Correct |
14 ms |
34796 KB |
Output is correct |
18 |
Correct |
19 ms |
34796 KB |
Output is correct |
19 |
Correct |
18 ms |
34796 KB |
Output is correct |
20 |
Correct |
20 ms |
34796 KB |
Output is correct |
21 |
Correct |
17 ms |
34796 KB |
Output is correct |
22 |
Correct |
23 ms |
34796 KB |
Output is correct |
23 |
Correct |
19 ms |
34796 KB |
Output is correct |
24 |
Correct |
24 ms |
34796 KB |
Output is correct |
25 |
Correct |
196 ms |
34796 KB |
Output is correct |
26 |
Correct |
328 ms |
34796 KB |
Output is correct |
27 |
Correct |
514 ms |
34796 KB |
Output is correct |
28 |
Correct |
586 ms |
34796 KB |
Output is correct |
29 |
Correct |
841 ms |
34796 KB |
Output is correct |
30 |
Correct |
741 ms |
34796 KB |
Output is correct |