| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53593 |
2018-06-30T09:17:45 Z |
0^0(#1412) |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
60900 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf = 1e18;
int sz = 1 << 19;
struct SGT {
pair<ll, ll> tree[1 << 20];
SGT() {
for (int i = 0; i < (1 << 20); i++)
tree[i] = { -inf,-inf };
}
void update(int idx, ll val) {
idx += sz;
tree[idx].first = val;
idx /= 2;
while (idx) {
tree[idx] = ((tree[idx * 2].first + tree[idx * 2].second > tree[idx * 2 + 1].first + tree[idx * 2 + 1].second) ? tree[idx * 2] : tree[idx * 2 + 1]);
idx /= 2;
}
}
ll query(int le, int ri) {
le += sz;
ri += sz;
ll ret = -inf * 3;
while (le <= ri) {
if (le & 1) {
ret=max(ret, tree[le].first + tree[le].second);
le++;
}
if (!(ri & 1)){
ret=max(ret, tree[ri].first + tree[ri].second);
ri--;
}
le /= 2;
ri /= 2;
}
return ret;
}
};
int n, u, d, s;
vector<pair<int, int> > vec[500005];
SGT le, ri;
int main() {
scanf("%d%d%d%d", &n, &u, &d, &s);
for (int i = 0; i < 500005; i++) {
ri.tree[sz + i].second = -u * i;
le.tree[sz + (500004 - i)].second = -d * i;
}
le.tree[sz + s].first = 0;
ri.tree[sz + s].first = 0;
for (int i = sz - 1; i > 0; i--) {
le.tree[i] = ((le.tree[i * 2].first + le.tree[i * 2].second > le.tree[i * 2 + 1].first + le.tree[i * 2 + 1].second) ? le.tree[i * 2] : le.tree[i * 2 + 1]);
ri.tree[i] = ((ri.tree[i * 2].first + ri.tree[i * 2].second > ri.tree[i * 2 + 1].first + ri.tree[i * 2 + 1].second) ? ri.tree[i * 2] : ri.tree[i * 2 + 1]);
}
for (int i = 0; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
vec[a].emplace_back(b, c);
}
for (int i = 0; i < 500005; i++) {
if (vec[i].empty())continue;
sort(vec[i].begin(), vec[i].end());
vector<ll> dd(vec[i].size()), ld(vec[i].size()), rd(vec[i].size());
for (int j = 0; j < vec[i].size(); j++) {
int idx = vec[i][j].first;
int cost = vec[i][j].second;
int lidx = 0;
int ridx = 500004;
ll now = le.query(lidx, idx - 1) + d * (500004 - idx) + cost;
now = max(now, ri.query(idx + 1, ridx) + u * idx + cost);
dd[j] = now;
}
ld[0] = dd[0];
for (int j = 1; j < vec[i].size(); j++)
ld[j] = max(dd[j], ld[j - 1] - d * (vec[i][j].first - vec[i][j - 1].first) + vec[i][j].second);
rd[vec[i].size() - 1] = dd[vec[i].size() - 1];
for (int j = (int)vec[i].size() - 2; j >= 0; j--)
rd[j] = max(dd[j], rd[j + 1] - u * (vec[i][j + 1].first - vec[i][j].first) + vec[i][j].second);
for (int j = 0; j < vec[i].size(); j++) {
le.update(vec[i][j].first, max(ld[j], rd[j]));
ri.update(vec[i][j].first, max(ld[j], rd[j]));
}
}
ll ans = 0;
for (int i = 0; i < 500005; i++) {
ll now = ri.tree[sz + i].first - (s > i ? (s - i)*d : (i - s)*u);
ans = max(ans, now);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec[i].size(); j++) {
~~^~~~~~~~~~~~~~~
salesman.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < vec[i].size(); j++)
~~^~~~~~~~~~~~~~~
salesman.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec[i].size(); j++) {
~~^~~~~~~~~~~~~~~
salesman.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &u, &d, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
44792 KB |
Output is correct |
| 2 |
Correct |
50 ms |
44900 KB |
Output is correct |
| 3 |
Correct |
50 ms |
44976 KB |
Output is correct |
| 4 |
Correct |
53 ms |
44992 KB |
Output is correct |
| 5 |
Correct |
62 ms |
45248 KB |
Output is correct |
| 6 |
Correct |
84 ms |
45684 KB |
Output is correct |
| 7 |
Correct |
164 ms |
46604 KB |
Output is correct |
| 8 |
Correct |
228 ms |
48152 KB |
Output is correct |
| 9 |
Correct |
310 ms |
49812 KB |
Output is correct |
| 10 |
Correct |
570 ms |
54484 KB |
Output is correct |
| 11 |
Correct |
603 ms |
54628 KB |
Output is correct |
| 12 |
Correct |
782 ms |
57752 KB |
Output is correct |
| 13 |
Correct |
882 ms |
57752 KB |
Output is correct |
| 14 |
Execution timed out |
1094 ms |
60772 KB |
Time limit exceeded |
| 15 |
Correct |
941 ms |
60804 KB |
Output is correct |
| 16 |
Correct |
997 ms |
60900 KB |
Output is correct |
| 17 |
Correct |
51 ms |
60900 KB |
Output is correct |
| 18 |
Correct |
52 ms |
60900 KB |
Output is correct |
| 19 |
Correct |
58 ms |
60900 KB |
Output is correct |
| 20 |
Correct |
65 ms |
60900 KB |
Output is correct |
| 21 |
Correct |
60 ms |
60900 KB |
Output is correct |
| 22 |
Correct |
64 ms |
60900 KB |
Output is correct |
| 23 |
Correct |
60 ms |
60900 KB |
Output is correct |
| 24 |
Correct |
54 ms |
60900 KB |
Output is correct |
| 25 |
Correct |
219 ms |
60900 KB |
Output is correct |
| 26 |
Correct |
325 ms |
60900 KB |
Output is correct |
| 27 |
Correct |
477 ms |
60900 KB |
Output is correct |
| 28 |
Correct |
503 ms |
60900 KB |
Output is correct |
| 29 |
Correct |
652 ms |
60900 KB |
Output is correct |
| 30 |
Correct |
622 ms |
60900 KB |
Output is correct |
