#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];
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];
if(j){
lm[j] = max(lm[j],
MUS.get(l, r) + u * p[j - 1] - 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];
if(j < k - 1){
rm[j] = max(rm[j],
PDS.get(l, r) - d * p[j + 1] - u * (p[j + 1] - p[j]) + s[j]);
}
}
for(int j = 0; j < k; j++) upd(p[j], max(lm[j], rm[j]));
}
printf("%d\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: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 |
44 ms |
43768 KB |
Output is correct |
| 2 |
Correct |
41 ms |
43768 KB |
Output is correct |
| 3 |
Correct |
42 ms |
43952 KB |
Output is correct |
| 4 |
Correct |
44 ms |
44028 KB |
Output is correct |
| 5 |
Correct |
46 ms |
44412 KB |
Output is correct |
| 6 |
Correct |
77 ms |
45920 KB |
Output is correct |
| 7 |
Correct |
124 ms |
48820 KB |
Output is correct |
| 8 |
Correct |
188 ms |
53528 KB |
Output is correct |
| 9 |
Correct |
289 ms |
58236 KB |
Output is correct |
| 10 |
Correct |
402 ms |
72316 KB |
Output is correct |
| 11 |
Correct |
565 ms |
72464 KB |
Output is correct |
| 12 |
Correct |
650 ms |
81852 KB |
Output is correct |
| 13 |
Correct |
797 ms |
81852 KB |
Output is correct |
| 14 |
Correct |
817 ms |
91008 KB |
Output is correct |
| 15 |
Correct |
665 ms |
91132 KB |
Output is correct |
| 16 |
Correct |
787 ms |
91132 KB |
Output is correct |
| 17 |
Incorrect |
40 ms |
91132 KB |
Output isn't correct |
| 18 |
Incorrect |
42 ms |
91132 KB |
Output isn't correct |
| 19 |
Incorrect |
42 ms |
91132 KB |
Output isn't correct |
| 20 |
Incorrect |
51 ms |
91132 KB |
Output isn't correct |
| 21 |
Incorrect |
51 ms |
91132 KB |
Output isn't correct |
| 22 |
Incorrect |
50 ms |
91132 KB |
Output isn't correct |
| 23 |
Incorrect |
45 ms |
91132 KB |
Output isn't correct |
| 24 |
Incorrect |
53 ms |
91132 KB |
Output isn't correct |
| 25 |
Incorrect |
125 ms |
91132 KB |
Output isn't correct |
| 26 |
Incorrect |
241 ms |
91132 KB |
Output isn't correct |
| 27 |
Incorrect |
335 ms |
91132 KB |
Output isn't correct |
| 28 |
Incorrect |
452 ms |
91132 KB |
Output isn't correct |
| 29 |
Incorrect |
407 ms |
91132 KB |
Output isn't correct |
| 30 |
Incorrect |
439 ms |
91132 KB |
Output isn't correct |
