#include <bits/stdc++.h>
using namespace std;
const int N = 500005, m = 500001, INF = 1000000009;
int ka()
{
int x = 0;
while (1)
{
char y = getchar();
if ('0' <= y && y <= '9')
x = (x * 10) + (y - '0');
else
return x;
}
}
struct ban
{
int t, x, m;
};
bool operator<(const ban& a, const ban& b)
{
return a.t < b.t;
}
bool so1(const ban& a, const ban& b)
{
return a.x < b.x;
}
int n;
int d, u;
int s;
ban a[N];
vector<int> t1, t2;
void ubd(vector<int>& t, int tl, int tr, int l, int r, int b, int k, int pos)
{
if (l > r)
return;
if (tl == l && tr == r)
{
t[pos] = max(t[pos], b);
return;
}
int m = (tl + tr) / 2;
ubd(t, tl, m, l, min(m, r), b, k, pos * 2);
ubd(t, m + 1, tr, max(m + 1, l), r, b, k, pos * 2 + 1);
}
int qry(vector<int>& t, int tl, int tr, int x, int k, int pos)
{
if (tl == tr)
{
return t[pos] + (k * x);
}
int m = (tl + tr) / 2;
if (x <= m)
return max(qry(t, tl, m, x, k, pos * 2), t[pos] + (k * x));
else
return max(qry(t, m + 1, tr, x, k, pos * 2 + 1), t[pos] + (k * x));
}
void solv1()
{
sort(a + 1, a + n + 1);
t1.assign(4 * N, -INF);
t2.assign(4 * N, -INF);
ubd(t1, 1, m, 1, s, -s * d, d, 1);
ubd(t2, 1, m, s, m, s * u, -u, 1);
for (int i = 1; i <= n; ++i)
{
int ans = max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m;
ubd(t1, 1, m, 1, a[i].x, ans - a[i].x * d, d, 1);
ubd(t2, 1, m, a[i].x, m, ans + a[i].x * u, -u, 1);
}
int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1));
printf("%d\n", ans);
}
vector<ban> v[N];
int ansv[N];
int qryy[N];
int main()
{
//freopen("input.txt", "r", stdin);
//scanf("%d%d%d%d", &n, &d, &u, &s);
n = ka();
d = ka();
u = ka();
s = ka();
for (int i = 1; i <= n; ++i)
{
//scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
a[i].t = ka();
a[i].x = ka();
a[i].m = ka();
}
//solv1();
for (int i = 1; i <= n; ++i)
v[a[i].t].push_back(a[i]);
t1.assign(4 * N, -INF);
t2.assign(4 * N, -INF);
ubd(t1, 1, m, 1, s, -s * d, d, 1);
ubd(t2, 1, m, s, m, s * u, -u, 1);
for (int i = 1; i < N; ++i)
{
if (v[i].empty())
continue;
sort(v[i].begin(), v[i].end(), so1);
int vs = v[i].size();
for (int j = 0; j < vs; ++j)
{
ansv[j] = -INF;
qryy[j] = max(qry(t1, 1, m, v[i][j].x, d, 1), qry(t2, 1, m, v[i][j].x, -u, 1)) + v[i][j].m;
}
int yans = -INF;
for (int j = 0; j < vs; ++j)
{
if (j)
yans -= (v[i][j].x - v[i][j - 1].x) * u;
int yansv = -INF;
yansv = qryy[j];
yansv = max(yansv, yans + v[i][j].m);
yans = max(yans, yansv);
ansv[j] = max(ansv[j], yansv);
}
yans = -INF;
for (int j = (int)vs - 1; j >= 0; --j)
{
if (j != (int)vs - 1)
yans -= (v[i][j + 1].x - v[i][j].x) * d;
int yansv = -INF;
yansv = qryy[j];
yansv = max(yansv, yans + v[i][j].m);
yans = max(yans, yansv);
ansv[j] = max(ansv[j], yansv);
}
for (int j = 0; j < vs; ++j)
{
int ans = ansv[j];//max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m;
ubd(t1, 1, m, 1, v[i][j].x, ans - v[i][j].x * d, d, 1);
ubd(t2, 1, m, v[i][j].x, m, ans + v[i][j].x * u, -u, 1);
}
}
int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1));
printf("%d\n", ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27768 KB |
Output is correct |
| 2 |
Correct |
22 ms |
27768 KB |
Output is correct |
| 3 |
Correct |
22 ms |
27768 KB |
Output is correct |
| 4 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
28 ms |
28024 KB |
Output is correct |
| 6 |
Correct |
63 ms |
28536 KB |
Output is correct |
| 7 |
Correct |
115 ms |
29944 KB |
Output is correct |
| 8 |
Correct |
198 ms |
32120 KB |
Output is correct |
| 9 |
Correct |
299 ms |
34168 KB |
Output is correct |
| 10 |
Correct |
469 ms |
40696 KB |
Output is correct |
| 11 |
Correct |
574 ms |
40824 KB |
Output is correct |
| 12 |
Correct |
743 ms |
45108 KB |
Output is correct |
| 13 |
Correct |
804 ms |
45180 KB |
Output is correct |
| 14 |
Correct |
948 ms |
49528 KB |
Output is correct |
| 15 |
Correct |
815 ms |
49272 KB |
Output is correct |
| 16 |
Correct |
968 ms |
49400 KB |
Output is correct |
| 17 |
Correct |
25 ms |
27768 KB |
Output is correct |
| 18 |
Correct |
23 ms |
27896 KB |
Output is correct |
| 19 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 20 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 21 |
Correct |
27 ms |
27768 KB |
Output is correct |
| 22 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 23 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 24 |
Correct |
31 ms |
27896 KB |
Output is correct |
| 25 |
Correct |
160 ms |
30584 KB |
Output is correct |
| 26 |
Correct |
266 ms |
33456 KB |
Output is correct |
| 27 |
Correct |
445 ms |
37604 KB |
Output is correct |
| 28 |
Correct |
530 ms |
37740 KB |
Output is correct |
| 29 |
Correct |
669 ms |
40904 KB |
Output is correct |
| 30 |
Correct |
686 ms |
41768 KB |
Output is correct |
