#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define INF 1000000000
using namespace std;
const int MAX=4e5+100;
const int N=3e5+5;
const int MOD = 1e9 + 7;
/*
----------------------------------------------------------------------------------
|
BBBBBBBBBB LL BBBBBBBBBB DDDDDDDD DDDDDDD III N N |
BB BB LL BB BB DD DD DD DD III NN N |
BB BB LL BB BB DD DD DD DD III N N N |
BBBBBBBBBB LL BBBBBBBBBB DD DD DD DD III N N N |
BB BB LL BB BB DD DD DD DD III N N N |
BB BB LL BB BB DD DD DD DD III N N N |
BB BB LL BB BB DD DD DD DD III N NN |
BB BB LLLLLLLL BB BB DDDDDDDD DDDDDDD III N N |
|
----------------------------------------------------------------------------------
*/
int par[MAX],sz[MAX];
int get(int a){
if(par[a]==-1)return a;
return par[a]=get(par[a]);
}
bool unite(int a,int b){
a=get(a);
b=get(b);
if(a==b)return false;
if(sz[a]>sz[b])swap(a,b);
sz[b]+=sz[a];
par[a]=b;
return true;
}
void solve(){
int n;cin>>n;
vector<int>v(n+1);
for(int i=1;i<=n;i++){
cin>>v[i];
}
vector<array<int,3>>g;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int cost;
if(v[i]<=v[j])cost = min(v[i],v[j] % v[i]);
else cost = min(v[j],v[i] % v[j]);
g.push_back({cost,i,j});
}
}
sort(all(g));
memset(par,-1,sizeof(par));
fill(sz,sz + MAX,1);
int ans=0,cnt=0;
for(auto [w,a,b] : g){
if(unite(a,b)){
ans+=w;
cnt++;
if(cnt==n-1)break;
}
}
cout<<ans<<endl;
}
signed main(){
int t=1;//cin>>t;
while(t--){
solve();
}
}
# | 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... |
# | 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... |