#include<bits/stdc++.h>
using namespace std;
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
using ll = long long;
const int N = 1e5;
int n, i, p, nxt, par[N], answer;
int asc(int x){
return par[x] < 0 ? x : par[x] = asc(par[x]);
}
void join(int u, int v, int w){
u = asc(u), v = asc(v);
if(u != v){
answer += w;
par[u] = v;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
vector<int> a(n);
for(i = 0; i < n; i++){
cin >> a[i];
par[i] = -1;
}
sort(all(a)), compact(a);
vector<pair<int, pair<int,int>>> E;
for(i = sz(a) - 1; i >= 0; i--){
nxt = a[i], p = lower_bound(1 + i + all(a), nxt) - a.begin();
while(p < sz(a)){
if(a[p] % a[i] < a[0]) E.push_back(make_pair(a[p] % a[i], make_pair(i, p)));
nxt += a[i];
p = lower_bound(1 + i + all(a), nxt) - a.begin();
}
}
sort(all(E));
for(auto i : E){
join(i.second.first, i.second.second, i.first);
}
cout << answer << "\n";
return 0;
}
# | 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... |