#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int parent[MAXN];
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return false;
parent[pa] = pb;
return true;
}
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n;i++) cin >> p[i];
vector<tuple<int, int, int>> edges;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n;j++) {
int cost = min(p[i] % p[j], p[j] % p[i]);
edges.emplace_back(cost, i, j);
}
}
sort(edges.begin(), edges.end());
for (int i = 0; i < n; ++i) parent[i] = i;
long long total = 0;
int count = 0;
for (auto [cost, u, v] : edges) {
if (unite(u, v)) {
total += cost;
count++;
if (count == n - 1) break;
}
}
cout << total << 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... |
# | 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... |