#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 500005, sz = 524288, INF = int(1e9);
struct Seg{
int d[2 * sz];
void ini(){ fill(d + 1, d + 2 * sz, -INF); }
int upd(int x, int v){
x += sz;
d[x] = max(d[x], v);
for(x >>= 1; x; x >>= 1) d[x] = max(d[2 * x], d[2 * x + 1]);
}
int get(int s, int e){
int r = -INF;
for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
if( s & 1) r = max(r, d[s++]);
if(~e & 1) r = max(r, d[e--]);
}
return r;
}
} PDS, MUS;
int n, d, u, sx, lm[N], rm[N], ln[N], rn[N];
vector<pii> v[N];
vector<int> s[N], p[N];
void upd(int x, int v){
PDS.upd(x, v + d * x);
MUS.upd(x, v - u * x);
}
int main(){
scanf("%d%d%d%d", &n, &d, &u, &sx);
for(int x, y, z; n--; ){
scanf("%d%d%d", &x, &y, &z);
v[x].push_back({y, z});
}
s[N - 1].push_back(0);
p[N - 1].push_back(sx);
for(int i = 1; i < N; i++){
sort(v[i].begin(), v[i].end());
for(pii j : v[i]){
p[i].push_back(j.first);
s[i].push_back(j.second);
}
}
PDS.ini(); MUS.ini();
upd(sx, 0);
for(int t = 1; t < N; t++){
vector<int> &p = ::p[t], &s = ::s[t];
int k = s.size();
for(int j = 0; j < k; j++){
int l = (j ? p[j - 1] : 0) + 1, r = p[j];
lm[j] = PDS.get(l, r) - d * p[j] + s[j];
ln[j] = s[j];
if(j){
lm[j] = max({lm[j],
MUS.get(l, r) + u * p[j - 1] - d * (p[j] - p[j - 1])
+ ln[j - 1] + s[j],
lm[j - 1] - d * (p[j] - p[j - 1]) + s[j]});
ln[j] = max(ln[j], ln[j - 1] - (u + d) * (p[j] - p[j - 1]) + s[j]);
}
}
for(int j = k - 1; j >= 0; j--){
int l = p[j], r = (j < k - 1 ? p[j + 1] : sz) - 1;
rm[j] = MUS.get(l, r) + u * p[j] + s[j];
rn[j] = s[j];
if(j < k - 1){
rm[j] = max({rm[j],
PDS.get(l, r) - d * p[j + 1] - u * (p[j + 1] - p[j])
+ rn[j + 1] + s[j],
rm[j + 1] - u * (p[j + 1] - p[j]) + s[j]});
rn[j] = max(rn[j], rn[j + 1] - (u + d) * (p[j + 1] - p[j]) + s[j]);
}
}
for(int j = 0; j < k; j++) upd(p[j], max(lm[j], rm[j]));
}
printf("%lld\n", PDS.get(sx, sx) - d * sx);
}
Compilation message
salesman.cpp: In member function 'int Seg::upd(int, int)':
salesman.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
salesman.cpp: In function 'int main()':
salesman.cpp:81:46: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n", PDS.get(sx, sx) - d * sx);
~~~~~~~~~~~~~~~~~~~~~~~~^
salesman.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &d, &u, &sx);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
43896 KB |
Output is correct |
2 |
Correct |
42 ms |
44008 KB |
Output is correct |
3 |
Correct |
42 ms |
44008 KB |
Output is correct |
4 |
Correct |
52 ms |
44104 KB |
Output is correct |
5 |
Correct |
50 ms |
44396 KB |
Output is correct |
6 |
Correct |
83 ms |
45804 KB |
Output is correct |
7 |
Correct |
137 ms |
48616 KB |
Output is correct |
8 |
Correct |
239 ms |
53456 KB |
Output is correct |
9 |
Correct |
298 ms |
58164 KB |
Output is correct |
10 |
Correct |
432 ms |
72116 KB |
Output is correct |
11 |
Correct |
550 ms |
72204 KB |
Output is correct |
12 |
Correct |
638 ms |
81640 KB |
Output is correct |
13 |
Correct |
673 ms |
81656 KB |
Output is correct |
14 |
Correct |
797 ms |
91072 KB |
Output is correct |
15 |
Correct |
678 ms |
91204 KB |
Output is correct |
16 |
Correct |
808 ms |
91204 KB |
Output is correct |
17 |
Correct |
41 ms |
91204 KB |
Output is correct |
18 |
Correct |
44 ms |
91204 KB |
Output is correct |
19 |
Correct |
42 ms |
91204 KB |
Output is correct |
20 |
Correct |
49 ms |
91204 KB |
Output is correct |
21 |
Correct |
44 ms |
91204 KB |
Output is correct |
22 |
Correct |
48 ms |
91204 KB |
Output is correct |
23 |
Correct |
51 ms |
91204 KB |
Output is correct |
24 |
Correct |
49 ms |
91204 KB |
Output is correct |
25 |
Correct |
137 ms |
91204 KB |
Output is correct |
26 |
Correct |
212 ms |
91204 KB |
Output is correct |
27 |
Correct |
361 ms |
91204 KB |
Output is correct |
28 |
Correct |
443 ms |
91204 KB |
Output is correct |
29 |
Correct |
518 ms |
91204 KB |
Output is correct |
30 |
Correct |
454 ms |
91204 KB |
Output is correct |