| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 198935 |
2020-01-28T08:34:29 Z |
SamAnd |
Salesman (IOI09_salesman) |
C++17 |
|
1000 ms |
58232 KB |
#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;
}
int n;
int d, u;
int s;
ban a[N];
bool so1(const int i, const int j)
{
return a[i].x < a[j].x;
}
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<int> v[N];
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(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);
for (int j = 0; j < v[i].size(); ++j)
ansv[j] = -INF;
int yans = -INF;
for (int j = 0; j < v[i].size(); ++j)
{
if (j)
yans -= (a[v[i][j]].x - a[v[i][j - 1]].x) * u;
int yansv = -INF;
yansv = max(qry(t1, 1, m, a[v[i][j]].x, d, 1), qry(t2, 1, m, a[v[i][j]].x, -u, 1)) + a[v[i][j]].m;
yansv = max(yansv, yans + a[v[i][j]].m);
yans = max(yans, yansv);
ansv[j] = max(ansv[j], yansv);
}
yans = -INF;
for (int j = (int)v[i].size() - 1; j >= 0; --j)
{
if (j != (int)v[i].size() - 1)
yans -= (a[v[i][j + 1]].x - a[v[i][j]].x) * d;
int yansv = -INF;
yansv = max(qry(t1, 1, m, a[v[i][j]].x, d, 1), qry(t2, 1, m, a[v[i][j]].x, -u, 1)) + a[v[i][j]].m;
yansv = max(yansv, yans + a[v[i][j]].m);
yans = max(yans, yansv);
ansv[j] = max(ansv[j], yansv);
}
for (int j = 0; j < v[i].size(); ++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, a[v[i][j]].x, ans - a[v[i][j]].x * d, d, 1);
ubd(t2, 1, m, a[v[i][j]].x, m, ans + a[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;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:89:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:110:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:73: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:75: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 |
23 ms |
27772 KB |
Output is correct |
| 2 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 3 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 4 |
Correct |
27 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
32 ms |
27896 KB |
Output is correct |
| 6 |
Correct |
69 ms |
28664 KB |
Output is correct |
| 7 |
Correct |
148 ms |
29816 KB |
Output is correct |
| 8 |
Correct |
273 ms |
32120 KB |
Output is correct |
| 9 |
Correct |
382 ms |
34168 KB |
Output is correct |
| 10 |
Correct |
634 ms |
40716 KB |
Output is correct |
| 11 |
Correct |
824 ms |
40728 KB |
Output is correct |
| 12 |
Execution timed out |
1045 ms |
51108 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1041 ms |
51464 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1095 ms |
58232 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1077 ms |
57460 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1083 ms |
57208 KB |
Time limit exceeded |
| 17 |
Correct |
26 ms |
27768 KB |
Output is correct |
| 18 |
Correct |
26 ms |
27768 KB |
Output is correct |
| 19 |
Correct |
25 ms |
27768 KB |
Output is correct |
| 20 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 21 |
Correct |
27 ms |
27768 KB |
Output is correct |
| 22 |
Correct |
31 ms |
27768 KB |
Output is correct |
| 23 |
Correct |
32 ms |
27768 KB |
Output is correct |
| 24 |
Correct |
33 ms |
27896 KB |
Output is correct |
| 25 |
Correct |
234 ms |
29560 KB |
Output is correct |
| 26 |
Correct |
395 ms |
31336 KB |
Output is correct |
| 27 |
Correct |
760 ms |
34184 KB |
Output is correct |
| 28 |
Correct |
738 ms |
34136 KB |
Output is correct |
| 29 |
Execution timed out |
1090 ms |
36172 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1016 ms |
36592 KB |
Time limit exceeded |
