#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k, n; cin >> k >> n;
if ( k == 1 ){
int C = 0;
vector <int> p;
for ( int i = 0; i < n; i++ ){
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if ( a == b ){
C += abs(x - y);
}
else{
p.pb(x), p.pb(y);
}
}
sort(all(p));
int sz = (int)p.size(), Mn = 1e18;
if ( !sz ) Mn = 0;
int pref = 0, suff = accumulate(all(p), 0ll);
for ( int i = 0; i < sz; i++ ){
suff -= p[i];
chmin(Mn, i * p[i] - pref + suff - (sz - i - 1) * p[i]);
pref += p[i];
}
cout << Mn + C + sz / 2 << ln;
return 0;
}
int C = 0;
vector <pair<int,int>> p;
for ( int i = 0; i < n; i++ ){
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if ( a == b ){
C += abs(x - y);
}
else{
if ( x > y ) swap(x, y);
p.pb({x, y});
}
}
auto f = [&](vector <int> p){
sort(all(p));
int sz = (int)p.size(), Mn = 1e18;
if ( !sz ) Mn = 0;
int pref = 0, suff = accumulate(all(p), 0ll);
for ( int i = 0; i < sz; i++ ){
suff -= p[i];
chmin(Mn, i * p[i] - pref + suff - (sz - i - 1) * p[i]);
pref += p[i];
}
return Mn + sz / 2;
};
int Mn = p.empty() ? 0 : 1e18;
sort(all(p));
vector <int> v, q;
for ( int i = (int)p.size() - 1; i >= 0; i-- ){
q.pb(p[i].first), q.pb(p[i].second);
}
for ( int i = 0; i < (int)p.size(); i++ ){
v.pb(p[i].first); v.pb(p[i].second);
q.pop_back(); q.pop_back();
chmin(Mn, f(q) + f(v));
}
cout << Mn + C;
cout << '\n';
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
# |
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 |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
20 ms |
2656 KB |
Output is correct |
13 |
Correct |
37 ms |
2512 KB |
Output is correct |
14 |
Correct |
27 ms |
2444 KB |
Output is correct |
15 |
Correct |
23 ms |
1388 KB |
Output is correct |
16 |
Correct |
25 ms |
2512 KB |
Output is correct |
17 |
Correct |
26 ms |
2512 KB |
Output is correct |
18 |
Correct |
32 ms |
2512 KB |
Output is correct |
19 |
Correct |
37 ms |
2512 KB |
Output is correct |
20 |
Correct |
25 ms |
2436 KB |
Output is correct |
21 |
Correct |
32 ms |
2476 KB |
Output is correct |
# |
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 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
5 |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
5 |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |