# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1281426 | StefanSebez | Palembang Bridges (APIO15_bridge) | C++20 | 82 ms | 1560 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
void chmn(ll &x,ll y){x=min(x,y);}
void chmx(ll &x,ll y){x=max(x,y);}
const ll inf=1e18;
void Solve1(){
int n;scanf("%i",&n);
vector<int>vals;
ll ans=0;
for(int i=1;i<=n;i++){
char p,q;int s,t;
cin>>p>>s>>q>>t;
if(p==q) ans+=abs(s-t);
else{
ans++;
vals.pb(s);vals.pb(t);
}
}
sort(vals.begin(),vals.end());
int m=vals.size()/2;
for(auto i:vals) ans+=abs(i-vals[m]);
printf("%lld\n",ans);
}
void Solve2(){
int n;scanf("%i",&n);
vector<ll>vals;
vector<pair<ll,ll>>a;
ll ans=0;
for(int i=1;i<=n;i++){
char p,q;ll s,t;
cin>>p>>s>>q>>t;
if(p==q) ans+=abs(s-t);
else{
ans++;
vals.pb(s);vals.pb(t);
if(s>t)swap(s,t);
a.pb({s,t});
}
}
ll res=inf;
for(auto i:vals){
for(auto j:vals){
ll sum=0;
for(auto [x,y]:a){
sum+=min(abs(x-i)+abs(y-i),abs(x-j)+abs(y-j));
}
chmn(res,sum);
}
}
ans+=res;
printf("%lld\n",ans);
}
int main(){
int KK;scanf("%i",&KK);
if(KK==1) Solve1();
else Solve2();
return 0;
}
Compilation message (stderr)
# | 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... |