#include<bits/stdc++.h>
using namespace std;
struct node{
char p,q;
long long s,t;
void inn(){
cin>>p>>s>>q>>t;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int k,n;cin>>k>>n;
vector<node>arr(n);
vector<long long>brr;
for (int i = 0;i<n;++i){
arr[i].inn();
if (arr[i].p!=arr[i].q){
brr.push_back(arr[i].s);
brr.push_back(arr[i].t);
}
}
const long long mxn = 1e18;
long long ans = mxn;
sort(brr.begin(),brr.end());
if (k == 1 || brr.size() <= 1){
for (int i = 0;i<2;++i){
long long curans = 0;
int temp = (int)brr.size()/2 - 1 + i;
for (int j = 0;j<n;++j){
if (arr[j].p == arr[j].q){
curans+=abs(arr[j].t - arr[j].s);
}
else{
curans+=abs(arr[j].t - brr[temp]) + abs(arr[j].s - brr[temp]) + 1;
}
}
ans = min(ans,curans);
}
}
if (k == 2 && (int)brr.size() > 1){
for (int x = 0;x<(int)brr.size();++x){
for (int y = 0;y<(int)brr.size();++y){
long long curans = 0;
for (int j = 0;j<n;++j){
if (arr[j].p == arr[j].q){
curans+=abs(arr[j].t - arr[j].s);
}
else{
curans+=min(llabs(arr[j].t - brr[x]) + llabs(arr[j].s - brr[x]),llabs(arr[j].t - brr[y]) + llabs(arr[j].s - brr[y])) + 1LL;
}
}
ans = min(curans,ans);
}
}
}
cout<<ans<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
12 |
Correct |
22 ms |
4836 KB |
Output is correct |
13 |
Correct |
37 ms |
4792 KB |
Output is correct |
14 |
Correct |
30 ms |
4528 KB |
Output is correct |
15 |
Correct |
23 ms |
2824 KB |
Output is correct |
16 |
Correct |
26 ms |
4848 KB |
Output is correct |
17 |
Correct |
27 ms |
4812 KB |
Output is correct |
18 |
Correct |
34 ms |
4816 KB |
Output is correct |
19 |
Correct |
40 ms |
4728 KB |
Output is correct |
20 |
Correct |
28 ms |
4816 KB |
Output is correct |
21 |
Correct |
35 ms |
4804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
8 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
11 ms |
324 KB |
Output is correct |
8 |
Correct |
15 ms |
324 KB |
Output is correct |
9 |
Correct |
12 ms |
316 KB |
Output is correct |
10 |
Correct |
11 ms |
328 KB |
Output is correct |
11 |
Correct |
12 ms |
324 KB |
Output is correct |
12 |
Correct |
13 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
8 ms |
324 KB |
Output is correct |
4 |
Correct |
10 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
11 ms |
212 KB |
Output is correct |
8 |
Correct |
11 ms |
328 KB |
Output is correct |
9 |
Correct |
12 ms |
320 KB |
Output is correct |
10 |
Correct |
11 ms |
324 KB |
Output is correct |
11 |
Correct |
11 ms |
212 KB |
Output is correct |
12 |
Correct |
11 ms |
212 KB |
Output is correct |
13 |
Execution timed out |
2082 ms |
340 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
9 ms |
324 KB |
Output is correct |
4 |
Correct |
8 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
12 ms |
324 KB |
Output is correct |
8 |
Correct |
11 ms |
328 KB |
Output is correct |
9 |
Correct |
12 ms |
212 KB |
Output is correct |
10 |
Correct |
11 ms |
212 KB |
Output is correct |
11 |
Correct |
11 ms |
212 KB |
Output is correct |
12 |
Correct |
12 ms |
212 KB |
Output is correct |
13 |
Execution timed out |
2073 ms |
340 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |