#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 7;
constexpr ll oo = 2e18;
ll total;
pair<ll, ll> T[MAXN];
vector<ll> Z;
int n, k;
ll check(ll l, ll r){
ll res = 0;
for(int i = 1; i <= n; i++){
if(T[i].first == -1) continue;
if(T[i].first <= l && l <= T[i].second) continue;
if(T[i].first <= r && r <= T[i].second) continue;
ll cost1 = min(abs(T[i].first - l), abs(T[i].second-l));
ll cost2 = min(abs(T[i].first - r), abs(T[i].second-r));
res += 2*min(cost1, cost2);
}
return res;
}
ll solve(){
ll res = oo;
if(k == 2){
for(int i = 0; i < Z.size(); i++)
for(int j = i; j < Z.size(); j++)
res = min(res, check(Z[i], Z[j]));
}
else {
for(int j = 0; j < Z.size(); j++)
res = min(res, check(Z[j], Z[j]));
}
return res;
}
int main(){
cin >> k >> n;
for(int i = 1; i <= n; i++){
char x, y;
ll a, b;
cin >> x >> a >> y >> b;
if(b < a) swap(a, b);
if(x != y){
total += (b-a+1);
T[i] = {a, b};
}
else{
total += (b-a);
T[i] = {-1, -1};
}
Z.push_back(a);
Z.push_back(b);
}
sort(Z.begin(), Z.end());
cout << total + solve() << "\n";
}
Compilation message
bridge.cpp: In function 'll solve()':
bridge.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < Z.size(); i++)
| ~~^~~~~~~~~~
bridge.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int j = i; j < Z.size(); j++)
| ~~^~~~~~~~~~
bridge.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int j = 0; j < Z.size(); j++)
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
3 ms |
444 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
516 KB |
Output is correct |
8 |
Correct |
5 ms |
348 KB |
Output is correct |
9 |
Correct |
10 ms |
344 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
7 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
8 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
7 ms |
348 KB |
Output is correct |
12 |
Execution timed out |
2101 ms |
4296 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
428 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
7 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
7 ms |
348 KB |
Output is correct |
11 |
Correct |
4 ms |
348 KB |
Output is correct |
12 |
Correct |
7 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
344 KB |
Output is correct |
8 |
Correct |
7 ms |
344 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
7 ms |
348 KB |
Output is correct |
11 |
Correct |
4 ms |
444 KB |
Output is correct |
12 |
Correct |
7 ms |
348 KB |
Output is correct |
13 |
Execution timed out |
2007 ms |
344 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
544 KB |
Output is correct |
8 |
Correct |
7 ms |
448 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
7 ms |
444 KB |
Output is correct |
11 |
Correct |
4 ms |
348 KB |
Output is correct |
12 |
Correct |
7 ms |
348 KB |
Output is correct |
13 |
Execution timed out |
2090 ms |
348 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |