# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
300113 |
2020-09-16T18:00:07 Z |
tatyam |
Salesman (IOI09_salesman) |
C++17 |
|
1410 ms |
35656 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
struct SegmentTree{
int n, cost;
vector<int> seg;
SegmentTree(int n, int cost): n(n), cost(cost), seg(n * 2, -INF){}
void set(int at, int val){
val += at * cost;
at += n;
seg[at] = val;
while(at /= 2) chmax(seg[at], val);
}
int get(int l, int r){
l += n; r += n;
int ans = -INF;
while(l < r){
if(l & 1) chmax(ans, seg[l++]);
if(r & 1) chmax(ans, seg[--r]);
l /= 2;
r /= 2;
}
return ans;
}
int down(int x){
return get(0, x + 1) - x * cost;
}
int up(int x){
return get(x, n) - x * cost;
}
};
int main(){
const int MAX = 500002;
int N, U, D, S;
cin >> N >> U >> D >> S;
vector<vector<array<int, 2>>> a(MAX);
for(int i = 0; i < N; i++){
int T, L, M;
cin >> T >> L >> M;
a[T].push_back({L, M});
}
SegmentTree up(MAX, -U), down(MAX, D);
up.set(S, 0);
down.set(S, 0);
for(auto& fairs : a) if(fairs.size()){
sort(fairs.begin(), fairs.end());
vector<int> dp_up(fairs.size()), dp_down;
for(int i = 0; i < fairs.size(); i++) dp_up[i] = max(down.down(fairs[i][0]), up.up(fairs[i][0]));
dp_down = dp_up;
dp_down[0] += fairs[0][1];
for(int i = 1; i < fairs.size(); i++){
chmax(dp_down[i], dp_down[i - 1] - D * (fairs[i][0] - fairs[i - 1][0]));
dp_down[i] += fairs[i][1];
}
dp_up.back() += fairs.back()[1];
for(int i = fairs.size() - 1; i--; ){
chmax(dp_up[i], dp_up[i + 1] - U * (fairs[i + 1][0] - fairs[i][0]));
dp_up[i] += fairs[i][1];
}
for(int i = 0; i < fairs.size(); i++){
up.set(fairs[i][0], max(dp_up[i], dp_down[i]));
down.set(fairs[i][0], max(dp_up[i], dp_down[i]));
}
}
cout << max(up.up(S), down.down(S)) << endl;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < fairs.size(); i++) dp_up[i] = max(down.down(fairs[i][0]), up.up(fairs[i][0]));
| ~~^~~~~~~~~~~~~~
salesman.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 1; i < fairs.size(); i++){
| ~~^~~~~~~~~~~~~~
salesman.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < fairs.size(); i++){
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
19840 KB |
Output is correct |
2 |
Correct |
17 ms |
19840 KB |
Output is correct |
3 |
Correct |
16 ms |
19968 KB |
Output is correct |
4 |
Correct |
19 ms |
19968 KB |
Output is correct |
5 |
Correct |
24 ms |
20096 KB |
Output is correct |
6 |
Correct |
66 ms |
20472 KB |
Output is correct |
7 |
Correct |
154 ms |
21496 KB |
Output is correct |
8 |
Correct |
293 ms |
22980 KB |
Output is correct |
9 |
Correct |
402 ms |
24692 KB |
Output is correct |
10 |
Correct |
723 ms |
29332 KB |
Output is correct |
11 |
Correct |
843 ms |
29276 KB |
Output is correct |
12 |
Correct |
1045 ms |
32468 KB |
Output is correct |
13 |
Correct |
1061 ms |
32460 KB |
Output is correct |
14 |
Correct |
1410 ms |
35600 KB |
Output is correct |
15 |
Correct |
1245 ms |
35656 KB |
Output is correct |
16 |
Correct |
1337 ms |
35552 KB |
Output is correct |
17 |
Correct |
16 ms |
19840 KB |
Output is correct |
18 |
Correct |
15 ms |
19840 KB |
Output is correct |
19 |
Correct |
16 ms |
19944 KB |
Output is correct |
20 |
Correct |
18 ms |
19968 KB |
Output is correct |
21 |
Correct |
19 ms |
19968 KB |
Output is correct |
22 |
Correct |
26 ms |
19968 KB |
Output is correct |
23 |
Correct |
22 ms |
19944 KB |
Output is correct |
24 |
Correct |
26 ms |
19968 KB |
Output is correct |
25 |
Correct |
210 ms |
21088 KB |
Output is correct |
26 |
Correct |
405 ms |
22136 KB |
Output is correct |
27 |
Correct |
641 ms |
23912 KB |
Output is correct |
28 |
Correct |
777 ms |
24160 KB |
Output is correct |
29 |
Correct |
935 ms |
24860 KB |
Output is correct |
30 |
Correct |
993 ms |
25544 KB |
Output is correct |