#include <bits/stdc++.h>
using namespace std;
const int lim = 5e5 + 2, Nmax = 5e5 + 10, inf = 2e9;
int dp[Nmax], x[Nmax], p[Nmax], come[Nmax];
int n, U, D;
vector<int> event[Nmax];
class AIB
{
int a[Nmax];
int ub(int x) { return (x&(-x)); }
public:
void init()
{
int i;
for(i=0; i<=lim; ++i) a[i] = -inf;
}
int query(int pos)
{
int ans = -inf;
for(; pos; pos-=ub(pos)) ans = max(ans, a[pos]);
return ans;
}
void update(int pos, int val)
{
for(; pos<=lim; pos+=ub(pos)) a[pos] = max(a[pos], val);
}
} aib1, aib2;
bool cmp(int a, int b)
{
return x[a] < x[b];
}
void solve(vector<int> &v)
{
if(v.empty()) return;
sort(v.begin(), v.end(), cmp);
for(auto pos : v)
come[pos] = max(aib1.query(x[pos]) - D * x[pos], aib2.query(lim - x[pos]) + U * x[pos]);
int sum = 0, best = -inf;
for(auto pos : v)
{
best = max(best, come[pos] + D * x[pos] - sum);
sum += p[pos];
dp[pos] = best + sum - D * x[pos];
}
sum = 0; best = -inf;
reverse(v.begin(), v.end());
for(auto pos : v)
{
best = max(best, come[pos] - U * x[pos] - sum);
sum += p[pos];
dp[pos] = max(dp[pos], best + sum + U * x[pos]);
}
for(auto pos : v)
{
aib1.update(x[pos], dp[pos] + D * x[pos]);
aib2.update(lim - x[pos], dp[pos] - U * x[pos]);
}
}
int main()
{
// freopen("input", "r", stdin);
int i, day, S, n;
cin.sync_with_stdio(false);
cin >> n >> U >> D >> S;
for(i=1; i<=n; ++i)
{
cin >> day >> x[i] >> p[i];
event[day].push_back(i);
}
event[lim+1].push_back(n+1);
x[n+1] = S; p[n+1] = 0;
aib1.init(); aib2.init();
aib1.update(S, D * S);
aib2.update(lim - S, -U*S);
for(i=1; i<=lim+1; ++i) solve(event[i]);
cout << dp[n+1] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
16000 KB |
Output is correct |
2 |
Correct |
18 ms |
16000 KB |
Output is correct |
3 |
Correct |
19 ms |
16128 KB |
Output is correct |
4 |
Correct |
19 ms |
16128 KB |
Output is correct |
5 |
Correct |
20 ms |
16384 KB |
Output is correct |
6 |
Correct |
42 ms |
17016 KB |
Output is correct |
7 |
Correct |
74 ms |
18424 KB |
Output is correct |
8 |
Correct |
137 ms |
20728 KB |
Output is correct |
9 |
Correct |
211 ms |
23160 KB |
Output is correct |
10 |
Correct |
442 ms |
30240 KB |
Output is correct |
11 |
Correct |
464 ms |
30196 KB |
Output is correct |
12 |
Correct |
668 ms |
34936 KB |
Output is correct |
13 |
Correct |
585 ms |
34852 KB |
Output is correct |
14 |
Correct |
734 ms |
39544 KB |
Output is correct |
15 |
Correct |
845 ms |
39548 KB |
Output is correct |
16 |
Correct |
737 ms |
39544 KB |
Output is correct |
17 |
Correct |
21 ms |
16000 KB |
Output is correct |
18 |
Correct |
19 ms |
16000 KB |
Output is correct |
19 |
Correct |
22 ms |
16128 KB |
Output is correct |
20 |
Correct |
18 ms |
16128 KB |
Output is correct |
21 |
Correct |
22 ms |
16128 KB |
Output is correct |
22 |
Correct |
20 ms |
16128 KB |
Output is correct |
23 |
Correct |
19 ms |
16128 KB |
Output is correct |
24 |
Correct |
19 ms |
16128 KB |
Output is correct |
25 |
Correct |
67 ms |
18168 KB |
Output is correct |
26 |
Correct |
138 ms |
20216 KB |
Output is correct |
27 |
Correct |
284 ms |
23596 KB |
Output is correct |
28 |
Correct |
369 ms |
23624 KB |
Output is correct |
29 |
Correct |
360 ms |
26556 KB |
Output is correct |
30 |
Correct |
390 ms |
26364 KB |
Output is correct |