#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz size()
const int N = 1e5 + 5;
ll jogap, a[N], b[N];
int n, k;
char oy[N], of[N];
vector <ll> v;
ll hasapla (ll x, ll y) {
ll ret = 0;
for (int i = 1; i <= n; ++i) {
if (oy[i] == of[i]) {
ret += abs (a[i] - b[i]);
}
else {
ll gosh = abs (a[i] - x) + abs (x - b[i]) + 1;
ll gosh1 = 2e18;
if (k > 1)
gosh1 = abs (a[i] - y) + abs (y - b[i]) + 1;
ret += min (gosh, gosh1);
}
}
return ret;
}
int main () {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen ("input.txt", "r", stdin);
cin >> k >> n;
for (int i = 1; i <= n; ++i) {
cin >> oy[i] >> a[i] >> of[i] >> b[i];
}
ll goshmaly = 0;
jogap = 2e18;
for (int i = 1; i <= n; ++i) {
if (oy[i] == of[i]) {
goshmaly += abs (a[i] - b[i]);
}
else v.pb (a[i]);v.pb (b[i]);
}
// goshmaly += (ll)v.sz;
sort (v.begin(), v.end());
for (int i = 0; i < 2 * n; ++i) {
if (k > 1)
for (int j = i + 1; j < 2 * n; ++j) {
jogap = min (jogap, hasapla (v[i], v[j]));
}
else {
jogap = min (jogap, hasapla (v[i], -1));
}
}
if (jogap == 2e18) jogap = goshmaly;
// cout << jogap + goshmaly;
cout << jogap;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:41:3: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
41 | else v.pb (a[i]);v.pb (b[i]);
| ^~~~
bridge.cpp:41:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
41 | else v.pb (a[i]);v.pb (b[i]);
| ^
# |
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 |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
5 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
348 KB |
Output is correct |
7 |
Correct |
4 ms |
524 KB |
Output is correct |
8 |
Correct |
4 ms |
344 KB |
Output is correct |
9 |
Correct |
4 ms |
360 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
4 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
4 ms |
348 KB |
Output is correct |
4 |
Correct |
4 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
348 KB |
Output is correct |
7 |
Correct |
4 ms |
348 KB |
Output is correct |
8 |
Correct |
4 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
488 KB |
Output is correct |
12 |
Execution timed out |
2076 ms |
4312 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 |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
484 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
344 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
7 ms |
348 KB |
Output is correct |
12 |
Correct |
6 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
500 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
476 KB |
Output is correct |
6 |
Correct |
0 ms |
600 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
344 KB |
Output is correct |
11 |
Correct |
6 ms |
344 KB |
Output is correct |
12 |
Correct |
6 ms |
348 KB |
Output is correct |
13 |
Execution timed out |
2090 ms |
348 KB |
Time limit exceeded |
14 |
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 |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
444 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
344 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
6 ms |
476 KB |
Output is correct |
12 |
Correct |
6 ms |
348 KB |
Output is correct |
13 |
Execution timed out |
2098 ms |
348 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |