Hi everyone,

I’ve been doing this problem and used a \mathcal{O}(N \log N) 2P sort of approach to do it. It’s very similar to that described in the editorial, but it still seems to TLE.

```
#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <algorithm>
using namespace std; // too many things to use, i give up
// https://codeforces.com/contest/1627/problem/E (sample omitted due to length)
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
int test_num;
cin >> test_num;
for (int t = 0; t < test_num; t++) {
int floor_num, room_num;
int ladder_num;
// cout << "init done" << endl;
cin >> floor_num >> room_num >> ladder_num;
vector<long long> floors(floor_num);
for (long long& f : floors) {
cin >> f;
}
// cout << "floors done" << endl;
vector<vector<int>> floor_starts(floor_num);
vector<vector<int>> floor_ends(floor_num);
map<pair<int, int>, vector<pair<pair<int, int>, int>>> ladders;
for (int l = 0; l < ladder_num; l++) {
int s_floor, s_room;
int e_floor, e_room;
int health;
cin >> s_floor >> s_room >> e_floor >> e_room >> health;
assert(s_floor < e_floor);
floor_starts[--s_floor].push_back(--s_room);
floor_ends[--e_floor].push_back(--e_room);
ladders[{s_floor, s_room}].push_back({{e_floor, e_room}, health});
}
floor_starts[floor_num - 1].push_back(room_num - 1);
floor_ends[0].push_back(0);
// cout << "ladders done" << endl;
for (int f = 0; f < floor_num; f++) {
sort(floor_starts[f].begin(), floor_starts[f].end());
sort(floor_ends[f].begin(), floor_ends[f].end());
}
vector<map<int, long long>> min_cost(floor_num);
min_cost[0][0] = 0;
for (int f = 0; f < floor_num; f++) {
map<int, long long>& curr = min_cost[f];
if (curr.empty()) {
continue;
}
vector<int> ends;
for (int e : floor_ends[f]) {
if (curr.count(e)) {
ends.push_back(e);
}
}
vector<long long> pref_min(ends.size());
pref_min[0] = curr[ends[0]];
for (int e = 1; e < ends.size(); e++) {
pref_min[e] = std::min(
curr.count(ends[e]) ? curr[ends[e]] : INT64_MAX,
pref_min[e - 1] + floors[f] * (ends[e] - ends[e - 1])
);
}
vector<long long> suff_min(ends.size());
suff_min[ends.size() - 1] = curr[ends[ends.size() - 1]];
for (int e = ends.size() - 2; e >= 0; e--) {
suff_min[e] = std::min(
curr.count(ends[e]) ? curr[ends[e]] : INT64_MAX,
suff_min[e + 1] + floors[f] * (ends[e + 1] - ends[e])
);
}
int end_at = 0;
for (int s : floor_starts[f]) {
while (end_at < ends.size() && ends[end_at] <= s) {
end_at++;
}
curr[s] = INT64_MAX;
if (end_at > 0) {
curr[s] =
pref_min[end_at - 1] + floors[f] * (s - ends[end_at - 1]);
}
if (end_at < ends.size()) {
curr[s] = std::min(
curr[s],
suff_min[end_at] + floors[f] * (ends[end_at] - s)
);
}
if (f != floor_num || s != room_num) {
for (auto [next, hp] : ladders[{f, s}]) {
if (!min_cost[next.first].count(next.second)) {
min_cost[next.first][next.second] = INT64_MAX;
}
long long& dest = min_cost[next.first][next.second];
dest = std::min(dest, curr[s] - hp);
}
}
}
}
if (!min_cost[floor_num - 1].count(room_num - 1)) {
cout << "NO ESCAPE" << '\n';
} else {
cout << min_cost[floor_num - 1][room_num - 1] << '\n';
}
}
}
```

The thing is, I added the debug prints that are commented out in the example code, and it seems that the majority of the time is taken on IO! Is there any reason for this? Or is adding these debug prints just a bad way to profile my code?