#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
#define int long long // maybe tle?
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;
TcT> bool minimize(T &val, const T &upd) { return upd < val ? val = upd, 1 : 0; }
TcT> bool maximize(T &val, const T &upd) { return upd > val ? val = upd, 1 : 0; }
TcT, class S> istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second; }
TcT, class S> ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
int testcases = 1;
#define TC 0
if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */
int k, n;
int same_side;
vector <pair <int, int>> opposite;
struct Median {
int sum = 0;
priority_queue <int> left;
priority_queue <int, vector <int>, greater <int>> right;
void insert(int x) {
if (left.empty() || x <= left.top()) {
sum -= x;
left.push(x);
if (sz(left) > sz(right) + 1) {
x = left.top(); left.pop();
right.push(x);
sum += 2 * x;
}
} else {
sum += x;
right.push(x);
if (sz(right) > sz(left)) {
x = right.top(); right.pop();
left.push(x);
sum -= 2 * x;
}
}
}
};
void solve() {
cin >> k >> n;
for (int i = 1; i <= n; ++i) {
char p, q; int s, t; cin >> p >> s >> q >> t;
if (p == q)
same_side += abs(s - t);
else
opposite.emplace_back(min(s, t), max(s, t)), ++same_side;
}
if (opposite.empty())
return void(cout << same_side << '\n');
sort(all(opposite), [&](pair <int, int> a, pair <int, int> b) -> bool {
return a.first + a.second < b.first + b.second;
});
n = sz(opposite);
vector <int> pref(n + 1);
Median Med;
for (int i = 0; i < n; ++i) {
Med.insert(opposite[i].first);
Med.insert(opposite[i].second);
pref[i + 1] = Med.sum;
}
int ans = pref[n];
if (k == 2) {
Med = Median();
for (int i = n; i >= 1; --i) {
Med.insert(opposite[i].first);
Med.insert(opposite[i].second);
minimize(ans, pref[i] + Med.sum);
}
}
cout << ans + same_side << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
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 |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
17 ms |
5624 KB |
Output is correct |
13 |
Correct |
37 ms |
5972 KB |
Output is correct |
14 |
Correct |
28 ms |
5072 KB |
Output is correct |
15 |
Correct |
21 ms |
3544 KB |
Output is correct |
16 |
Correct |
18 ms |
5588 KB |
Output is correct |
17 |
Correct |
30 ms |
5696 KB |
Output is correct |
18 |
Correct |
20 ms |
5844 KB |
Output is correct |
19 |
Correct |
36 ms |
5492 KB |
Output is correct |
20 |
Correct |
32 ms |
5868 KB |
Output is correct |
21 |
Correct |
33 ms |
5588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |