| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 198939 |
2020-01-28T08:36:40 Z |
SamAnd |
Salesman (IOI09_salesman) |
C++17 |
|
1000 ms |
49440 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;
}
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 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);
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 -= (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[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 -= (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[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, 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;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:85:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:88:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
salesman.cpp:109: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 |
26 ms |
27768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
27768 KB |
Output is correct |
| 3 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 4 |
Correct |
26 ms |
27896 KB |
Output is correct |
| 5 |
Correct |
30 ms |
27896 KB |
Output is correct |
| 6 |
Correct |
64 ms |
28664 KB |
Output is correct |
| 7 |
Correct |
139 ms |
29944 KB |
Output is correct |
| 8 |
Correct |
243 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
349 ms |
34424 KB |
Output is correct |
| 10 |
Correct |
612 ms |
40696 KB |
Output is correct |
| 11 |
Correct |
714 ms |
40824 KB |
Output is correct |
| 12 |
Correct |
950 ms |
45048 KB |
Output is correct |
| 13 |
Execution timed out |
1025 ms |
45048 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1097 ms |
49440 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1026 ms |
49400 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1098 ms |
49400 KB |
Time limit exceeded |
| 17 |
Correct |
24 ms |
27772 KB |
Output is correct |
| 18 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 19 |
Correct |
25 ms |
27772 KB |
Output is correct |
| 20 |
Correct |
29 ms |
27768 KB |
Output is correct |
| 21 |
Correct |
30 ms |
27768 KB |
Output is correct |
| 22 |
Correct |
30 ms |
27896 KB |
Output is correct |
| 23 |
Correct |
30 ms |
27896 KB |
Output is correct |
| 24 |
Correct |
34 ms |
27896 KB |
Output is correct |
| 25 |
Correct |
207 ms |
30456 KB |
Output is correct |
| 26 |
Correct |
371 ms |
33204 KB |
Output is correct |
| 27 |
Correct |
632 ms |
37344 KB |
Output is correct |
| 28 |
Correct |
639 ms |
37596 KB |
Output is correct |
| 29 |
Correct |
928 ms |
40952 KB |
Output is correct |
| 30 |
Correct |
906 ms |
41432 KB |
Output is correct |
