# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
300078 |
2020-09-16T13:07:23 Z |
tatyam |
Salesman (IOI09_salesman) |
C++17 |
|
1120 ms |
65540 KB |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int INF = 0x3fffffff;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
#define rep(n) for(int i = 0; i < n; i++)
#define rrep(n) for(int i = n; --i; )
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
int n, u, d, s;
struct T{
map<int, int> up;
map<int, int, greater<int>> down;
T(int s){
up[s] = 0;
down[s] = 0;
up[1000000] = -INF;
down[0] = -INF;
}
int operator[](int at){
int ans = -INF;
pii a = *up.lower_bound(at);
chmax(ans, a.second - (a.first - at) * u);
a = *down.lower_bound(at);
chmax(ans, a.second - (at - a.first) * d);
return ans;
}
void insert(int at, int val){
auto p = up.try_emplace(at, -INF).first;
if(chmax(p->second, val)){
while(p != up.begin()){
auto q = prev(p);
if(p->second - q->second >= (p->first - q->first) * u) up.erase(q);
else break;
}
}
p = down.try_emplace(at, -INF).first;
if(chmax(p->second, val)){
while(p != down.begin()){
auto q = prev(p);
if(p->second - q->second >= (q->first - p->first) * d) down.erase(q);
else break;
}
}
}
};
signed main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> u >> d >> s;
T q(s);
vector<tuplis> a(n);
each(i, a) each(j, i) cin >> j;
map<int, vector<pii>> b;
each(i, a) b[i[0]].emplace_back(i[1], i[2]);
a.clear();
a.shrink_to_fit();
for(auto& [_, a] : b){
int n = a.size();
sort(all(a));
vector<int> up(n), down;
rep(n) up[i] = q[a[i].first];
down = up;
rep(n){
down[i] += a[i].second;
if(i + 1 < n) chmax(down[i + 1], down[i] - (a[i + 1].first - a[i].first) * d);
}
rrep(n){
up[i] += a[i].second;
if(i) chmax(up[i - 1], up[i] - (a[i].first - a[i - 1].first) * u);
}
rep(n) q.insert(a[i].first, max(up[i], down[i]));
}
cout << q[s] << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
7 ms |
1152 KB |
Output is correct |
6 |
Correct |
26 ms |
3328 KB |
Output is correct |
7 |
Correct |
78 ms |
7928 KB |
Output is correct |
8 |
Correct |
191 ms |
15460 KB |
Output is correct |
9 |
Correct |
311 ms |
22648 KB |
Output is correct |
10 |
Correct |
695 ms |
45544 KB |
Output is correct |
11 |
Correct |
630 ms |
45688 KB |
Output is correct |
12 |
Correct |
1120 ms |
59768 KB |
Output is correct |
13 |
Correct |
970 ms |
60000 KB |
Output is correct |
14 |
Runtime error |
698 ms |
65540 KB |
Execution killed with signal 9 |
15 |
Runtime error |
696 ms |
65540 KB |
Execution killed with signal 9 |
16 |
Runtime error |
675 ms |
65540 KB |
Execution killed with signal 9 |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
19 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
20 |
Correct |
4 ms |
512 KB |
Output is correct |
21 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
22 |
Incorrect |
5 ms |
640 KB |
Output isn't correct |
23 |
Incorrect |
5 ms |
640 KB |
Output isn't correct |
24 |
Incorrect |
7 ms |
768 KB |
Output isn't correct |
25 |
Incorrect |
77 ms |
6136 KB |
Output isn't correct |
26 |
Incorrect |
204 ms |
12016 KB |
Output isn't correct |
27 |
Incorrect |
314 ms |
20832 KB |
Output isn't correct |
28 |
Correct |
528 ms |
23020 KB |
Output is correct |
29 |
Incorrect |
476 ms |
28152 KB |
Output isn't correct |
30 |
Incorrect |
440 ms |
29544 KB |
Output isn't correct |