#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MX = 500500;
struct Seg{
vector<ll> tree;
int sz;
void init(int n, vector<ll> &vec){
sz = n;
tree.resize(sz*2);
if (!vec.empty()) for (int i=0;i<sz;i++) tree[i+sz] = vec[i];
else fill(tree.begin()+sz, tree.begin()+sz*2, -1e18);
for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
void update(int x, ll val){
for (tree[x+=sz] = val;x>1;x>>=1) tree[x>>1] = max(tree[x], tree[x^1]);
}
ll query(int l, int r){
ll ret = -1e18;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = max(ret, tree[l++]);
if (r&1) ret = max(ret, tree[--r]);
}
return ret;
}
}tree1, tree2;
vector<pair<int, int>> a[500500];
ll dp[500500];
int main(){
int n, u, d, s;
scanf("%d %d %d %d", &n, &d, &u, &s);
for (int i=0;i<n;i++){
int t, l, m;
scanf("%d %d %d", &t, &l, &m);
a[t].emplace_back(l, m);
}
for (int i=1;i<MX;i++) sort(a[i].begin(), a[i].end());
fill(dp+1, dp+MX, -1e18);
dp[s] = 0;
vector<ll> tmp;
tree1.init(MX, tmp); tree2.init(MX, tmp);
tree1.update(s, dp[s]-s*d);
tree2.update(s, dp[s]-(MX-s)*u);
for (int T=1;T<MX;T++){
if (a[T].empty()) continue;
int sz = a[T].size();
vector<ll> ranL(sz+1, -1e18), ranR(sz+1, -1e18);
vector<ll> SL(sz), SR(sz);
SL[0] = a[T][0].second - (u+d)*a[T][0].first;
SR[sz-1] = a[T][sz-1].second - (u+d)*(MX-a[T][sz-1].first);
for (int i=1;i<sz;i++) SL[i] = SL[i-1] + a[T][i].second - (u+d)*(a[T][i].first-a[T][i-1].first);
for (int i=sz-2;i>=0;i--) SR[i] = SR[i+1] + a[T][i].second - (u+d)*(a[T][i+1].first-a[T][i].first);
vector<ll> TL(sz), TR(sz);
TL[0] = a[T][0].second - d*(a[T][0].first);
TR[sz-1] = a[T][sz-1].second - u*(MX-a[T][sz-1].first);
for (int i=1;i<sz;i++) TL[i] = TL[i-1] + a[T][i].second - d*(a[T][i].first-a[T][i-1].first);
for (int i=sz-2;i>=0;i--) TR[i] = TR[i+1] + a[T][i].second - u*(a[T][i+1].first-a[T][i].first);
Seg tree3, tree4;
tree3.init(sz, SL); tree4.init(sz, SR);
ll cur1 = 0;
for (int i=0;i<sz;i++){
cur1 += a[T][i].second;
int cur = a[T][i].first+1, nxt = MX;
if (i!=sz-1) nxt = a[T][i+1].first;
ll tmp1 = tree1.query(cur, nxt) + (d*(cur-1));
ll tmp2 = tree2.query(cur, nxt) - (d*(nxt-cur+1)) + (u*(MX-nxt));
tmp2 += tree3.query(i+1, sz) + (u+d)*nxt - cur1;
ranL[i] = max(tmp1, tmp2)+TL[i];
//if (a[T][i].first==75) printf("%lld %lld\n", tmp1, tmp2);
}
cur1 = 0;
for (int i=sz-1;i>=0;i--){
cur1 += a[T][i].second;
int cur = a[T][i].first, nxt = 1;
if (i) nxt = a[T][i-1].first+1;
ll tmp1 = tree2.query(nxt, cur) + (u*(MX-cur));
ll tmp2 = tree1.query(nxt, cur) - (u*(cur-nxt+1)) + (d*(nxt-1));
tmp2 += tree4.query(0, i) + (u+d)*(MX-(nxt-1)) - cur1;
ranR[i] = max(tmp1, tmp2)+TR[i];
}
Seg tree5, tree6;
tree5.init(sz, ranL); tree6.init(sz, ranR);
for (int i=0;i<sz;i++){
int cur = a[T][i].first;
ll tmp1 = tree5.query(i, sz) - TL[i] + a[T][i].second;
ll tmp2 = tree6.query(0, i+1) - TR[i] + a[T][i].second;
dp[cur] = max(tmp1, tmp2);
tree1.update(cur, dp[cur]-cur*d);
tree2.update(cur, dp[cur]-(MX-cur)*u);
//printf("%d: %lld %lld %lld\n", cur, dp[cur], tmp1, tmp2);
}
}
ll ans = 0;
for (int i=1;i<s;i++) ans = max(ans, dp[i] - u*(s-i));
for (int i=s+1;i<MX;i++) ans = max(ans, dp[i] - d*(i-s));
printf("%lld\n", ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d %d %d %d", &n, &d, &u, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d %d", &t, &l, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
31564 KB |
Output is correct |
| 2 |
Correct |
20 ms |
31656 KB |
Output is correct |
| 3 |
Correct |
21 ms |
31652 KB |
Output is correct |
| 4 |
Correct |
25 ms |
31616 KB |
Output is correct |
| 5 |
Correct |
26 ms |
31788 KB |
Output is correct |
| 6 |
Correct |
55 ms |
32252 KB |
Output is correct |
| 7 |
Correct |
123 ms |
33204 KB |
Output is correct |
| 8 |
Correct |
214 ms |
34756 KB |
Output is correct |
| 9 |
Correct |
294 ms |
36288 KB |
Output is correct |
| 10 |
Correct |
494 ms |
41188 KB |
Output is correct |
| 11 |
Correct |
611 ms |
41064 KB |
Output is correct |
| 12 |
Correct |
791 ms |
44152 KB |
Output is correct |
| 13 |
Correct |
778 ms |
44280 KB |
Output is correct |
| 14 |
Correct |
971 ms |
47288 KB |
Output is correct |
| 15 |
Correct |
862 ms |
47416 KB |
Output is correct |
| 16 |
Correct |
997 ms |
47292 KB |
Output is correct |
| 17 |
Correct |
21 ms |
31532 KB |
Output is correct |
| 18 |
Correct |
21 ms |
31660 KB |
Output is correct |
| 19 |
Correct |
22 ms |
31636 KB |
Output is correct |
| 20 |
Correct |
23 ms |
31724 KB |
Output is correct |
| 21 |
Correct |
22 ms |
31708 KB |
Output is correct |
| 22 |
Correct |
26 ms |
31824 KB |
Output is correct |
| 23 |
Correct |
24 ms |
31736 KB |
Output is correct |
| 24 |
Correct |
26 ms |
31824 KB |
Output is correct |
| 25 |
Correct |
136 ms |
33180 KB |
Output is correct |
| 26 |
Correct |
245 ms |
36860 KB |
Output is correct |
| 27 |
Correct |
378 ms |
42880 KB |
Output is correct |
| 28 |
Correct |
474 ms |
39260 KB |
Output is correct |
| 29 |
Correct |
595 ms |
37420 KB |
Output is correct |
| 30 |
Correct |
557 ms |
45576 KB |
Output is correct |
