# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
137968697 |
Practice:
Sturdy |
1513D
- 60
|
C++17 (GCC 7-32)
|
Wrong answer on test 3
|
78 ms
|
2536 KB
|
2021-12-04 12:22:25 |
2021-12-04 12:22:25 |
|
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
const int N = 100001;
using namespace std;
int f(ll n) {
return (1 + sqrt(1 + 8 * n)) / 2;
}
int main() {
// cout << fixed << setprecision(10);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int n, p;
cin >> n >> p;
bool vis[n];
memset(vis, false, sizeof vis);
pair<int, int> a[n];
int ar[n];
for (int i = 0; i < n; i++) {
cin >> a[i].first;
a[i].second = i;
ar[i] = a[i].first;
}
sort(a, a + n);
ll ans = 0;
int comp = 0;
for (auto [e, i] : a) {
if (vis[i]) continue;
int h = min(e, p);
comp++;
int j = i - 1;
while (j >= 0 && ar[j] % e == 0 && !vis[j]) {
vis[j--] = 1;
vis[i] = 1;
ans += h;
}
j = i + 1;
while (j < n && ar[j] % e == 0 && !vis[j]) {
vis[j++] = 1;
vis[i] = 1;
ans += h;
}
}
cout << ans + (ll) (comp - 1) * p << '\n';
}
}
// 4 5
// 5 2 4 9
Click to see test details