#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli maxn = lli(1e6)+5, inf = lli(1e15);
lli solve1(vector<lli>& B)
{
lli res = 0;
sort(B.begin(), B.end());
lli mid = B[(lli(B.size())-1)/2];
//cout << mid << "\n";
for(auto it: B) res += llabs(it-mid);
return res;
}
lli solve2(vector<pair<lli, lli>> A)
{
vector<lli> tmp;
for(lli i = 0;i < lli(A.size());i++)
{
if(A[i].first > A[i].second) swap(A[i].first, A[i].second);
tmp.push_back(A[i].first), tmp.push_back(A[i].second);
}
sort(A.begin(), A.end());
lli res = inf;
for(auto it: tmp)
{
lli cur = 0;
vector<lli> other;
for(lli i = 0;i < lli(A.size());i++)
{
if(A[i].first <= it) cur += abs(it-A[i].first), cur += abs(it-A[i].second);
else other.push_back(A[i].first), other.push_back(A[i].second);
}
cur += solve1(other);
//cout << it << " " << cur << "\n";
res = min(res, cur);
}
return res;
}
int main(void)
{
lli n, k, res = 0;
scanf("%lld%lld", &k, &n);
vector<pair<lli, lli>> A;
for(lli i = 0;i < n;i++)
{
string s, t;
lli a, b;
cin >> s >> a >> t >> b;
if(s == t) res += llabs(b-a);
else
{
A.push_back({a, b});
res++;
}
}
if(k-1) res += solve2(A);
else
{
vector<lli> tmp;
for(auto it: A) tmp.push_back(it.first), tmp.push_back(it.second);
res += solve1(tmp);
}
printf("%lld\n", res);
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:52:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &k, &n);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2024 KB |
Output is correct |
2 |
Correct |
0 ms |
2024 KB |
Output is correct |
3 |
Correct |
0 ms |
2024 KB |
Output is correct |
4 |
Correct |
0 ms |
2024 KB |
Output is correct |
5 |
Correct |
0 ms |
2024 KB |
Output is correct |
6 |
Correct |
0 ms |
2024 KB |
Output is correct |
7 |
Correct |
0 ms |
2024 KB |
Output is correct |
8 |
Correct |
0 ms |
2024 KB |
Output is correct |
9 |
Correct |
3 ms |
2024 KB |
Output is correct |
10 |
Correct |
0 ms |
2024 KB |
Output is correct |
11 |
Correct |
0 ms |
2024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2024 KB |
Output is correct |
2 |
Correct |
0 ms |
2024 KB |
Output is correct |
3 |
Correct |
0 ms |
2024 KB |
Output is correct |
4 |
Correct |
0 ms |
2024 KB |
Output is correct |
5 |
Correct |
3 ms |
2024 KB |
Output is correct |
6 |
Correct |
0 ms |
2024 KB |
Output is correct |
7 |
Correct |
0 ms |
2024 KB |
Output is correct |
8 |
Correct |
0 ms |
2024 KB |
Output is correct |
9 |
Correct |
0 ms |
2024 KB |
Output is correct |
10 |
Correct |
0 ms |
2024 KB |
Output is correct |
11 |
Correct |
0 ms |
2024 KB |
Output is correct |
12 |
Correct |
96 ms |
8252 KB |
Output is correct |
13 |
Correct |
176 ms |
8252 KB |
Output is correct |
14 |
Correct |
113 ms |
8252 KB |
Output is correct |
15 |
Correct |
89 ms |
5180 KB |
Output is correct |
16 |
Correct |
169 ms |
8252 KB |
Output is correct |
17 |
Correct |
153 ms |
8252 KB |
Output is correct |
18 |
Correct |
143 ms |
8252 KB |
Output is correct |
19 |
Correct |
199 ms |
8252 KB |
Output is correct |
20 |
Correct |
153 ms |
8252 KB |
Output is correct |
21 |
Correct |
156 ms |
8252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |