#include <bits/stdc++.h>
using namespace std;
const int N = 500005, m = 500001, INF = 1000000009;
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];
vector<int> ansv[N];
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &d, &u, &s);
for (int i = 1; i <= n; ++i)
scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
//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)
{
sort(v[i].begin(), v[i].end(), so1);
ansv[i].assign(v[i].size(), -INF);
int yans = -INF;
for (int j = 0; j < v[i].size(); ++j)
{
if (j)
yans -= (v[i][j].x - v[i][j - 1].x) * u;
int yansv = -INF;
yansv = 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;
yansv = max(yansv, yans + v[i][j].m);
yans = max(yans, yansv);
ansv[i][j] = max(ansv[i][j], yansv);
}
yans = -INF;
for (int j = (int)v[i].size() - 1; j >= 0; --j)
{
if (j != (int)v[i].size() - 1)
yans -= (v[i][j + 1].x - v[i][j].x) * d;
int yansv = -INF;
yansv = 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;
yansv = max(yansv, yans + v[i][j].m);
yans = max(yans, yansv);
ansv[i][j] = max(ansv[i][j], yansv);
}
for (int j = 0; j < v[i].size(); ++j)
{
int ans = ansv[i][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);
}
ansv[i].clear();
}
int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1));
printf("%d\n", ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:72: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, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
39416 KB |
Output is correct |
| 2 |
Correct |
35 ms |
39416 KB |
Output is correct |
| 3 |
Correct |
33 ms |
39544 KB |
Output is correct |
| 4 |
Correct |
37 ms |
39672 KB |
Output is correct |
| 5 |
Correct |
40 ms |
39800 KB |
Output is correct |
| 6 |
Correct |
78 ms |
40952 KB |
Output is correct |
| 7 |
Correct |
148 ms |
43128 KB |
Output is correct |
| 8 |
Correct |
279 ms |
46840 KB |
Output is correct |
| 9 |
Correct |
367 ms |
50808 KB |
Output is correct |
| 10 |
Correct |
622 ms |
63100 KB |
Output is correct |
| 11 |
Correct |
742 ms |
63608 KB |
Output is correct |
| 12 |
Runtime error |
746 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
733 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
561 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
510 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
568 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Correct |
33 ms |
39416 KB |
Output is correct |
| 18 |
Correct |
32 ms |
39544 KB |
Output is correct |
| 19 |
Correct |
35 ms |
39544 KB |
Output is correct |
| 20 |
Correct |
36 ms |
39544 KB |
Output is correct |
| 21 |
Correct |
36 ms |
39544 KB |
Output is correct |
| 22 |
Correct |
42 ms |
39672 KB |
Output is correct |
| 23 |
Correct |
42 ms |
39676 KB |
Output is correct |
| 24 |
Correct |
40 ms |
39672 KB |
Output is correct |
| 25 |
Correct |
226 ms |
42544 KB |
Output is correct |
| 26 |
Correct |
409 ms |
45596 KB |
Output is correct |
| 27 |
Correct |
656 ms |
49760 KB |
Output is correct |
| 28 |
Correct |
680 ms |
50836 KB |
Output is correct |
| 29 |
Correct |
953 ms |
54240 KB |
Output is correct |
| 30 |
Correct |
879 ms |
54484 KB |
Output is correct |
