#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 500005, sz = 524288;
const ll INF = ll(1e18);
struct Seg{
ll d[2 * sz];
void ini(){ fill(d + 1, d + 2 * sz, -INF); }
int upd(int x, ll 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]);
}
ll get(int s, int e){
ll 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;
ll lm[N], rm[N];
vector<pii> v[N];
vector<int> s[N], p[N];
void upd(int x, ll 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("%lld\n", PDS.get(sx, sx) - d * sx);
}
Compilation message
salesman.cpp: In member function 'int Seg::upd(int, ll)':
salesman.cpp:17:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
salesman.cpp: In function 'int main()':
salesman.cpp:39: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:41: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 |
47 ms |
51960 KB |
Output is correct |
| 2 |
Correct |
50 ms |
51960 KB |
Output is correct |
| 3 |
Correct |
49 ms |
52136 KB |
Output is correct |
| 4 |
Correct |
52 ms |
52188 KB |
Output is correct |
| 5 |
Correct |
56 ms |
52660 KB |
Output is correct |
| 6 |
Correct |
82 ms |
54056 KB |
Output is correct |
| 7 |
Correct |
147 ms |
56900 KB |
Output is correct |
| 8 |
Correct |
217 ms |
61676 KB |
Output is correct |
| 9 |
Correct |
273 ms |
66260 KB |
Output is correct |
| 10 |
Correct |
451 ms |
80412 KB |
Output is correct |
| 11 |
Correct |
589 ms |
80416 KB |
Output is correct |
| 12 |
Correct |
730 ms |
89832 KB |
Output is correct |
| 13 |
Correct |
710 ms |
89832 KB |
Output is correct |
| 14 |
Correct |
838 ms |
99232 KB |
Output is correct |
| 15 |
Correct |
858 ms |
99232 KB |
Output is correct |
| 16 |
Correct |
990 ms |
99232 KB |
Output is correct |
| 17 |
Incorrect |
50 ms |
99232 KB |
Output isn't correct |
| 18 |
Incorrect |
51 ms |
99232 KB |
Output isn't correct |
| 19 |
Incorrect |
53 ms |
99232 KB |
Output isn't correct |
| 20 |
Incorrect |
60 ms |
99232 KB |
Output isn't correct |
| 21 |
Incorrect |
57 ms |
99232 KB |
Output isn't correct |
| 22 |
Incorrect |
56 ms |
99232 KB |
Output isn't correct |
| 23 |
Incorrect |
53 ms |
99232 KB |
Output isn't correct |
| 24 |
Incorrect |
54 ms |
99232 KB |
Output isn't correct |
| 25 |
Incorrect |
145 ms |
99232 KB |
Output isn't correct |
| 26 |
Incorrect |
243 ms |
99232 KB |
Output isn't correct |
| 27 |
Incorrect |
405 ms |
99232 KB |
Output isn't correct |
| 28 |
Incorrect |
469 ms |
99232 KB |
Output isn't correct |
| 29 |
Incorrect |
483 ms |
99232 KB |
Output isn't correct |
| 30 |
Incorrect |
549 ms |
99232 KB |
Output isn't correct |
