| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53592 |
2018-06-30T09:15:56 Z |
0^0(#1412) |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
60920 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;
if (j)lidx = vec[i][j - 1].first + 1;
int ridx = 500004;
if (j + 1 < vec[i].size())ridx = vec[i][j + 1].first - 1;
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:70:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j + 1 < vec[i].size())ridx = vec[i][j + 1].first - 1;
~~~~~~^~~~~~~~~~~~~~~
salesman.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < vec[i].size(); j++)
~~^~~~~~~~~~~~~~~
salesman.cpp:81: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 |
51 ms |
44920 KB |
Output is correct |
| 2 |
Correct |
49 ms |
44988 KB |
Output is correct |
| 3 |
Correct |
50 ms |
44988 KB |
Output is correct |
| 4 |
Correct |
53 ms |
45016 KB |
Output is correct |
| 5 |
Correct |
58 ms |
45260 KB |
Output is correct |
| 6 |
Correct |
85 ms |
45828 KB |
Output is correct |
| 7 |
Correct |
180 ms |
46616 KB |
Output is correct |
| 8 |
Correct |
247 ms |
48212 KB |
Output is correct |
| 9 |
Correct |
378 ms |
49736 KB |
Output is correct |
| 10 |
Correct |
641 ms |
54540 KB |
Output is correct |
| 11 |
Correct |
714 ms |
54540 KB |
Output is correct |
| 12 |
Correct |
852 ms |
57804 KB |
Output is correct |
| 13 |
Correct |
823 ms |
57804 KB |
Output is correct |
| 14 |
Execution timed out |
1041 ms |
60792 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1062 ms |
60860 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1082 ms |
60920 KB |
Time limit exceeded |
| 17 |
Incorrect |
49 ms |
60920 KB |
Output isn't correct |
| 18 |
Incorrect |
50 ms |
60920 KB |
Output isn't correct |
| 19 |
Incorrect |
54 ms |
60920 KB |
Output isn't correct |
| 20 |
Incorrect |
57 ms |
60920 KB |
Output isn't correct |
| 21 |
Incorrect |
53 ms |
60920 KB |
Output isn't correct |
| 22 |
Incorrect |
56 ms |
60920 KB |
Output isn't correct |
| 23 |
Incorrect |
58 ms |
60920 KB |
Output isn't correct |
| 24 |
Correct |
55 ms |
60920 KB |
Output is correct |
| 25 |
Incorrect |
158 ms |
60920 KB |
Output isn't correct |
| 26 |
Incorrect |
371 ms |
60920 KB |
Output isn't correct |
| 27 |
Incorrect |
376 ms |
60920 KB |
Output isn't correct |
| 28 |
Incorrect |
539 ms |
60920 KB |
Output isn't correct |
| 29 |
Incorrect |
665 ms |
60920 KB |
Output isn't correct |
| 30 |
Incorrect |
541 ms |
60920 KB |
Output isn't correct |
