fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define int ll
  9. #define ii pair <int , int>
  10. #define iii pair <int , ii>
  11. #define se second
  12. #define fi first
  13. #define all(v) (v).begin() , (v).end()
  14. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  15. #define bit(x,i) (((x) >> (i)) & 1LL)
  16. #define flip(x,i) ((x) ^ (1LL << (i)))
  17. #define ms(d,x) memset(d , x , sizeof(d))
  18. #define exist __exist
  19. #define ends __ends
  20. #define visit visited
  21. #define left __left
  22. #define right __right
  23. #define prev __prev
  24. #define next __next
  25. #define sitingfake 1
  26. #define orz 1
  27. //constant
  28.  
  29. const long long mod = 1e9 + 7;
  30. const long long linf = 4557430888798830399LL;
  31. const long long nlinf = -4485090715960753727LL;
  32. const int inf = 1061109567;
  33. const int ninf = -1044266559;
  34. const int dx[] = {0 , -1 , 0 , 1};
  35. const int dy[] = {-1 , 0 , 1 , 0};
  36.  
  37. template<typename T> bool maximize(T &a, const T &b)
  38. {
  39.     if(a < b) {a = b; return 1;}
  40.     return 0;
  41. }
  42.  
  43. template<typename T> bool minimize(T &a, const T &b)
  44. {
  45.     if(a > b) {a = b; return 1;}
  46.     return 0;
  47. }
  48.  
  49. void Plus(ll & a ,ll b)
  50. {
  51.     b %= mod;
  52.     a += b;
  53.     if(a < 0) a += mod;
  54.     a %= mod;
  55.     return;
  56. }
  57.  
  58. void Mul(ll & a, ll b)
  59. {
  60.     (a *= (b % mod)) %= mod;
  61.     return;
  62. }
  63.  
  64. //code
  65. const int maxn = 5e5 + 7;
  66.  
  67. set <int> p;
  68.  
  69. int n;
  70.  
  71. ll a[maxn] , x , y , dp[2][3];
  72.  
  73. void Fact(ll X)
  74. {
  75.     for(ll i = 2; i * i <= X; i++)
  76.     {
  77.         if(X % i == 0)
  78.         {
  79.             p.insert(i);
  80.             while(X % i == 0)
  81.             {
  82.                 X /= i;
  83.             }
  84.         }
  85.     }
  86.     if(X > 1) p.insert(X);
  87. }
  88.  
  89. ll compute(int P)
  90. {
  91.     ms(dp , 0x3f);
  92.     dp[0][0] = 0;
  93.     for(int i = 1; i <= n; i++)
  94.     {
  95.         int cur = i & 1;
  96.         int pre = !cur;
  97.         ms(dp[cur] , 0x3f);
  98.         dp[cur][1] = min(dp[pre][1] , dp[pre][0]) + x;
  99.         if(a[i] % P == 0)
  100.         {
  101.             dp[cur][0] = dp[pre][0];
  102.             dp[cur][2] = min(dp[pre][1] , dp[pre][2]);
  103.         }
  104.         else if(((a[i] + 1) % P == 0) || ((a[i] - 1) % P == 0))
  105.         {
  106.             dp[cur][0] = dp[pre][0] + y;
  107.             dp[cur][2] = min(dp[pre][1] , dp[pre][2]) + y;
  108.         }
  109.     }
  110.     return min({dp[n & 1][0] , dp[n & 1][2] , dp[n & 1][1]});
  111. }
  112. void solve(void)
  113. {
  114.     cin >> n >> x >> y;
  115.     for(int i = 1; i <= n; i++) cin >> a[i];
  116.     Fact(a[1]);
  117.     Fact(a[1] + 1);
  118.     Fact(a[1] - 1);
  119.     Fact(a[n]);
  120.     Fact(a[n] + 1);
  121.     Fact(a[n] - 1);
  122.     ll ans = linf;
  123.  
  124.     for(int val : p)
  125.     {
  126.         ans = min(ans , compute(val));
  127.     }
  128.     cout << ans;
  129. }
  130. /**
  131. **/
  132. signed main()
  133. {
  134.    ios_base::sync_with_stdio(0);
  135.    cin.tie(0);
  136.    cout.tie(0);
  137.  
  138.    #define task "hsgs"
  139.  
  140.    if(fopen(task".inp","r"))
  141.    {
  142.        freopen(task".inp","r",stdin);
  143.        freopen(task".out","w",stdout);
  144.    }
  145.  
  146.    int tc = 1 , subtask; cin >> subtask;
  147. //   cin >> tc;
  148.    while(tc--) solve();
  149.  
  150. //   execute;
  151. }
  152.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4557430888798830399
https://ideone.com/GEA8cv
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!