fork download
  1. /*
  2.   Author: Cadocx
  3.   Codeforces: https://c...content-available-to-author-only...s.com/profile/Kadoc
  4.   VNOJ: oj.vnoi.info/user/Cadoc
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. // input/output
  11. #define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  12. #define el cout << '\n'
  13. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  14. // #pragma GCC optimize("O2", "unroll-loops", "Ofast")
  15. // #pragma GCC target("avx,avx2,fma")
  16. //data type
  17. #define ll long long
  18. #define ull unsigned long long
  19. #define pii pair<int, int>
  20. #define pll pair<ll, ll>
  21. #define piv pair<int, vector<int>>
  22. #define vi vector<int>
  23. #define vl vector<ll>
  24. #define vc vector<char>
  25. //STL
  26. #define sz(x) (int)(x).size()
  27. #define for1(i,l,r) for(auto i = l; i <= r; i++)
  28. #define for2(i,r,l) for(auto i = r; i >= l; i--)
  29. #define forin(i,a) for(auto i : a)
  30. #define pb push_back
  31. #define eb emplace_back
  32. #define pf push_front
  33. #define all(x) (x).begin(), (x).end()
  34. #define fi first
  35. #define se second
  36. //bitmask
  37. #define bitcnt(n) __builtin_popcount(n)
  38. #define mask(i) (1 << (i))
  39. #define bit(n, i) (((n) >> (i)) & 1)
  40. #define set_on(n, i) ((n) | mask(i))
  41. #define set_off(n, i) ((n) & ~mask(i))
  42. //constant
  43. #define N 100005
  44. #define MOD 1000230007
  45. #define INF 0x3f3f3f3f
  46. #define LINF 0x3f3f3f3f3f3f3f3f
  47. #define base 31
  48. #define Kadoc 0
  49.  
  50. int n, m, k, x, y, a[N], L[N], R[N];
  51. ll g[N][22], st[N << 2][22], dp[N][22];
  52.  
  53. int gcd(int l, int r){
  54. int k = 31 - __builtin_clz(r-l+1);
  55. return __gcd(g[l][k], g[r-mask(k)+1][k]);
  56. }
  57.  
  58. void upd(int j, int id, int l, int r, int i, ll x){
  59. if(i < l || r < i) return;
  60. if(l == r) return st[id][j] = x, void();
  61. int m = (l+r)>>1;
  62. upd(j, id<<1, l, m, i, x);
  63. upd(j, id<<1|1, m+1, r, i, x);
  64. st[id][j] = min(st[id<<1][j], st[id<<1|1][j]);
  65. }
  66.  
  67. ll get(int j, int id, int l, int r, int u, int v){
  68. if(u > v) return 1e18;
  69. if(v < l || r < u) return 1e18;
  70. if(u <= l && r <= v) return st[id][j];
  71. int m = (l+r)>>1;
  72. return min(get(j, id<<1, l, m, u, v), get(j, id<<1|1, m+1, r, u, v));
  73. }
  74.  
  75. void solve(){
  76. cin >> n >> m >> k >> x >> y;
  77. for(int i=1; i<=n; ++i) cin >> a[i], g[i][0] = a[i];
  78.  
  79. for(int j=1; mask(j)<=n; ++j) for(int i=1; i+mask(j)-1<=n; ++i)
  80. g[i][j] = __gcd(g[i][j-1], g[i+mask(j-1)][j-1]);
  81.  
  82. for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j) dp[i][j] = 1e18;
  83. for(int i=1; i<=n; ++i) upd(0, 1, 1, n, i, dp[i-1][0]);
  84. dp[0][0] = 0; upd(0, 1, 1, n, 1, 0);
  85.  
  86. L[0] = R[0] = 1;
  87. for(int i=1; i<=n; ++i){
  88. L[i] = L[i-1];
  89. R[i] = R[i-1];
  90.  
  91. while(L[i] <= i && gcd(L[i], i) < k) L[i]++;
  92.  
  93. while(R[i]+1 <= i && gcd(R[i]+1, i) <= k) R[i]++;
  94. }
  95.  
  96. for(int j=1; j<=m; ++j){
  97. for(int i=1; i<=n; ++i){
  98. if(gcd(L[i], i) != k){
  99. ll cur = get(j-1, 1, 1, n, 1, i);
  100. for(int l=1; l<=i; ++l) dp[i][j] = min(dp[i][j], cur + y);
  101. continue;
  102. }
  103.  
  104. ll curIn = get(j-1, 1, 1, n, L[i], R[i]);
  105. ll curOut = min(get(j-1, 1, 1, n, 1, L[i]-1), get(j-1, 1, 1, n, R[i]+1, i));
  106. dp[i][j] = min(dp[i][j], curIn + x);
  107. dp[i][j] = min(dp[i][j], curOut + y);
  108. }
  109.  
  110. for(int i=1; i<=n; ++i) upd(j, 1, 1, n, i, dp[i-1][j]);
  111. }
  112.  
  113. cout << dp[n][m];
  114. }
  115.  
  116. int main(){
  117. #define NAME "PYRAMID"
  118. if(fopen(NAME".inp", "r")){
  119. freopen(NAME".inp", "r", stdin);
  120. freopen(NAME".out", "w", stdout);
  121. }
  122.  
  123. fastIO;
  124.  
  125. if(Kadoc){
  126. int tc; cin >> tc;
  127. while(tc--){
  128. solve();
  129. }
  130. } else solve();
  131. }
  132.  
  133.  
Success #stdin #stdout 0.01s 5288KB
stdin
Standard input is empty
stdout
Standard output is empty