This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
vector <pair<long long,long long> > travels;
vector <long long> points;
long long cost(long long point){
long long ans=0;
for (auto a:travels) {
long long c,d;
c=a.first;
d=a.second;
ans+=abs(point-c) + abs(point-d);
}
return ans;
}
long long cost (long long point1, long long point2) {
long long ans=0;
for (auto a:travels) {
long long c,d;
c=a.first;
d=a.second;
ans+=min(abs(point1-c) + abs(point1-d),abs(point2-c) + abs(point2-d));
}
return ans;
}
int main() {
unordered_set<long long> unip;
int k,n;
cin >> k >> n;
long long sum=0;
rep(i,0,n) {
char a,b;
long long c,d;
cin >> a >> c >> b >> d;
if (a==b) {
sum+=abs(c-d);
}
else {
travels.push_back(make_pair(min(c,d),max(c,d)));
sum+=1;
unip.insert(c);
unip.insert(d);
}
}
for (auto x:unip) {
points.push_back(x);
}
if (k==1) {
sort(all(points));
int lo,hi;
lo=0;
hi=points.size()-1;
while (lo+2<hi) {
int mid1=lo+(hi-lo)/3;
int mid2=lo+(2*hi-2*lo)/3;
long long val1,val2;
val1=cost(points[mid1]);
val2=cost(points[mid2]);
if (val1<val2) hi=mid2;
else lo=mid1;
}
long long best=1000000000000000;
rep (i,lo,hi+1) {
best=min(best,cost(points[i]));
}
if (best==1000000000000000) best=0;
cout << best+sum << endl;
}
else {
sort(all(points));
//Hillclimb, two indicies: a and b, a<=b
if (points.size()==0) {
cout << sum << endl;
}
else {
long long best=cost(points[0],points[0]);
int besta,bestb;
besta=0;
bestb=0;
int m=points.size();
int stepsize=2*points.size()/3;
while (stepsize>2) {
int tempa,tempb;
tempa=besta;
tempb=bestb;
rep(i,-1,2) {
rep(j,-1,2) {
int a,b;
a=besta+i*stepsize;
b=bestb+j*stepsize;
if (a>b) continue;
if (a<0 || b>=m) continue;
long long currcost=cost(points[a],points[b]);
if (currcost<best) {
best=currcost;
tempa=a;
tempb=b;
}
}
}
besta=tempa;
bestb=tempb;
stepsize/=2;
}
rep (i, max(0,besta-3),min(m,besta+3)) {
rep (j, max(0,bestb-3), min(m,bestb+3)) {
best=min(best,cost(points[i],points[j]));
}
}
cout << sum+best << endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |