#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int k, n, S = 0;
cin >> k >> n;
vector<int> id, p, s, bp, bs;
for (int i = 0; i < n; i++)
{
char a, b;
int l, r;
cin >> a >> l >> b >> r;
if (l > r) swap(l, r);
if (a == b) S += r - l;
else id.push_back(l), id.push_back(r);
}
n = id.size();
if (n <= k)
{
cout << S << '\n';
return 0;
}
sort(id.begin(), id.end());
p = s = id;
for (int i = 1; i < n; i++) p[i] += p[i - 1];
for (int i = n - 2; i >= 0; i--) s[i] += s[i + 1];
bp.assign(n, 0), bs.assign(n, 0);
int res = inf;
for (int i = 0; i < n; i++)
{
res = min(res, s[i + 1] - p[i] + id[i] * (n - 2 * (n - i - 1)));
}
cout << res + S + n / 2 << '\n';
}
// bp[i] = s[i + 1] - p[i] + id[i] * (2 * (i + 1) - x)
// bs[i] = s[i + 1] - p[i] + id[i] * (x - 2 * (n - i - 1))
# |
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 |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 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 |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
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 |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
17 ms |
9172 KB |
Output is correct |
13 |
Correct |
32 ms |
10456 KB |
Output is correct |
14 |
Correct |
24 ms |
8648 KB |
Output is correct |
15 |
Correct |
19 ms |
6664 KB |
Output is correct |
16 |
Correct |
19 ms |
9916 KB |
Output is correct |
17 |
Correct |
22 ms |
10452 KB |
Output is correct |
18 |
Correct |
25 ms |
10188 KB |
Output is correct |
19 |
Correct |
31 ms |
10700 KB |
Output is correct |
20 |
Correct |
21 ms |
10144 KB |
Output is correct |
21 |
Correct |
28 ms |
10184 KB |
Output is correct |
# |
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 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
4 |
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 |
Incorrect |
0 ms |
412 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |