#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
ll INF=1e18+10;
int main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
int k,n;cin>>k>>n;
vector<pair<char,int>> a(n),b(n);
REP(i,0,n)cin>>a[i].F>>a[i].S>>b[i].F>>b[i].S;
//cout<<"a";
ll ans=0;
pii c;
REP(i,0,n){
if(a[i].F==b[i].F){
ans+=(ll)abs(a[i].S-b[i].S);
}
else {
if(a[i].S>b[i].S)swap(a[i].S,b[i].S);
c.PB({a[i].S,b[i].S});
}
}
int m=c.size();
if(m==0){
cout<<ans;
return 0;
}
if(m==1&&k==2){
ans+=abs(c[0].F-c[0].S);
cout<<ans;
return 0;
}
sort(c.begin(),c.end());
if(k==1){
vi ar;
REP(i,0,m)ar.PB(c[i].F);
REP(i,0,m)ar.PB(c[i].S);
sort(ar.begin(),ar.end());
REP(i,0,m*2)ans+=(ll)abs(ar[i]-ar[m]);
cout<<ans+(ll)m;
}
else{
ans+=(ll)m;
ll r=INF;
REP(i,0,m-1){
vi ar1,ar2;
ll tm=0;
REP(j,0,i+1){
ar1.PB(c[j].F);
ar1.PB(c[j].S);
}
REP(j,i+1,m){
ar2.PB(c[j].F);
ar2.PB(c[j].S);
}
sort(ar1.begin(),ar1.end());
sort(ar2.begin(),ar2.end());
int m1=ar1.size(),m2=ar2.size();
//cout<<m1<<" "<<m2<<"\n";
REP(j,0,m1)tm+=(ll)abs(ar1[j]-ar1[m1/2]);
REP(j,0,m2)tm+=(ll)abs(ar2[j]-ar2[m2/2]);
//cout<<tm<<"\n";
r=min(r,tm);
}
ans+=r;
cout<<ans;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 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 |
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 |
348 KB |
Output is correct |
12 |
Correct |
39 ms |
4168 KB |
Output is correct |
13 |
Correct |
82 ms |
4148 KB |
Output is correct |
14 |
Correct |
57 ms |
3992 KB |
Output is correct |
15 |
Correct |
47 ms |
2504 KB |
Output is correct |
16 |
Correct |
56 ms |
4296 KB |
Output is correct |
17 |
Correct |
80 ms |
4168 KB |
Output is correct |
18 |
Correct |
67 ms |
4292 KB |
Output is correct |
19 |
Correct |
91 ms |
4148 KB |
Output is correct |
20 |
Correct |
63 ms |
4296 KB |
Output is correct |
21 |
Correct |
78 ms |
4168 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 |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
544 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |