#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 1005;
int a[N], q[N];
struct E {
int a, b, w;
};
int findSet(int v) {
return q[v] < 0 ? v : q[v] = findSet(q[v]);
}
bool connect(int a, int b) {
a = findSet(a);
b = findSet(b);
if (a == b)
return false;
if (q[a] > q[b])
swap(a, b);
q[a] += q[b];
q[b] = a;
return true;
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
fill(q, q + n, -1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<E> edges;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edges.push_back({i, j, min(a[i] % a[j], a[j] % a[i])});
}
}
sort(all(edges), [](E x, E y) {
return x.w < y.w;
});
ll ans = 0;
for (E e : edges) {
if (connect(e.a, e.b)) {
ans += e.w;
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
6756 KB |
Output is correct |
2 |
Correct |
58 ms |
6624 KB |
Output is correct |
3 |
Correct |
67 ms |
6804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
6628 KB |
Output is correct |
2 |
Correct |
52 ms |
6752 KB |
Output is correct |
3 |
Correct |
68 ms |
6628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
6840 KB |
Output is correct |
2 |
Correct |
59 ms |
6628 KB |
Output is correct |
3 |
Correct |
73 ms |
6624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |