#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <sstream>
using namespace std;
using int64 = long long;
int N, M, K;
vector<pair<int64, int64>> segments;
vector<int64> X;
vector<int64> vec;
map<int64, int> idx;
int64 solve1brute() {
int64 res = (1LL<<60);
for (auto & x : vec) {
int64 cur = 0;
for (auto & s : segments) {
if (s.second < x) {
cur += 2 * (x - s.second);
} else if (s.second >= x && s.first <= x) {
// nada
} else {
cur += 2 * (s.first - x);
}
}
res = min(res, cur);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64 res = 0;
cin >> K >> N;
set<int> uniq;
for (int i = 0; i < N; i++) {
char z1, z2;
int x1, x2;
cin >> z1 >> x1 >> z2 >> x2;
res += abs(x1 - x2);
if (z1 != z2) {
segments.emplace_back(min(x1, x2), max(x1, x2));
uniq.insert(x1);
uniq.insert(x2);
}
}
if (!size(segments)) {
cout << res << "\n";
return 0;
}
vec = vector<int64>(begin(uniq), end(uniq));
N = size(vec);
for (int i = 0; i < N; i++) {
idx[vec[i]] = i;
}
M = size(segments);
res += M; // every crossed a bridge
// need at least one bridge;
cout << res + solve1brute() << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
4 ms |
508 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
352 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
5 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
3 ms |
584 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
5 ms |
588 KB |
Output is correct |
12 |
Correct |
18 ms |
3256 KB |
Output is correct |
13 |
Execution timed out |
2085 ms |
27792 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |