#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
long long BFG(vector<int>& neq)
{
int s=0;
int e=neq.size();
if(s==e)
return 0;
long long final=1e18;
long long sum=0,ot=0;
for(int j=s;j<e;j++)
sum+=neq[j];
for(int i=s;i<e;i++)
{
sum-=neq[i];
ot+=neq[i];
long long bf=i+1-s;
long long af=e-i-1;
final=min(final,(bf*((long long)(neq[i])))-ot + (sum-(af*((long long)neq[i]))));
}
return final;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k,n;
cin>>k>>n;
long long total=0;
vector<pair<int,int>> vlp;
vector<int> neq;
for(int j=0;j<n;j++)
{
char a,c;
int b,d;
cin>>a>>b>>c>>d;
if(a!=c)
{
neq.push_back(b);
neq.push_back(d);
vlp.push_back({b,d});
total+=1;
}
else
{
total+=abs(b-d);
}
}
sort(begin(neq),end(neq));
sort(begin(vlp),end(vlp));
if(k==1)
{
cout<<total+BFG(neq)<<'\n';
}
else
{
if(vlp.size()==0)
{
cout<<total<<'\n';
return 0;
}
long long pl=1e18;
for(int j=0;j<vlp.size();j++)
{
vector<int> fpp,spp;
for(int k=0;k<j;k++)
{
fpp.push_back(vlp[k].first);
fpp.push_back(vlp[k].second);
}
for(int k=j;k<vlp.size();k++)
{
spp.push_back(vlp[k].first);
spp.push_back(vlp[k].second);
}
sort(begin(fpp),end(fpp));
sort(begin(spp),end(spp));
pl=min(pl,BFG(fpp)+BFG(spp));
// if((BFG(0,j)+BFG(j+1,neq.size()))==5)
// {
// cout<<"For "<<j<<endl;
// }
}
cout<<total+pl<<'\n';
}
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int j=0;j<vlp.size();j++)
| ~^~~~~~~~~~~
bridge.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int k=j;k<vlp.size();k++)
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
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 |
344 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 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 |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
19 ms |
2244 KB |
Output is correct |
13 |
Correct |
39 ms |
2248 KB |
Output is correct |
14 |
Correct |
30 ms |
2000 KB |
Output is correct |
15 |
Correct |
22 ms |
1484 KB |
Output is correct |
16 |
Correct |
22 ms |
2248 KB |
Output is correct |
17 |
Correct |
28 ms |
2000 KB |
Output is correct |
18 |
Correct |
31 ms |
2244 KB |
Output is correct |
19 |
Correct |
43 ms |
2244 KB |
Output is correct |
20 |
Correct |
24 ms |
2244 KB |
Output is correct |
21 |
Correct |
33 ms |
2452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 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 |
- |