fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define name "vestonluvto"
  4. const char* namein = name ".inp";
  5. const char* nameout = name ".out";
  6.  
  7. #define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define PI 3.141592653589793238462
  9. #define sz(x) ((int)(x).size())
  10. #define all(x) (x).begin(), (x).end()
  11. #define pb emplace_back
  12.  
  13. using namespace std;
  14.  
  15. #ifndef LOCAL
  16. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  17. #else
  18. #define debug(x)
  19. #endif
  20.  
  21. void _print(int t) {cerr << t;}
  22. void _print(long long t) {cerr << t;}
  23. void _print(string t) {cerr << t;}
  24. void _print(char t) {cerr << t;}
  25. void _print(long double t) {cerr << t;}
  26. void _print(double t) {cerr << t;}
  27. void _print(unsigned long long t) {cerr << t;}
  28.  
  29. template <class T, class V> void _print(pair <T, V> p);
  30. template <class T> void _print(vector <T> v);
  31. template <class T> void _print(set <T> v);
  32. template <class T, class V> void _print(map <T, V> v);
  33. template <class T> void _print(multiset <T> v);
  34. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
  35. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  36. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  37. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  38. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  39.  
  40. void homefix(){
  41.     #ifndef LOCAL
  42.     freopen("fixcode.txt", "w", stderr);
  43.     #endif
  44. }
  45.  
  46. void home(){
  47.      homefix();
  48.      if (fopen(namein, "r")) {
  49.         freopen(namein, "r", stdin);
  50.         freopen(nameout, "w", stdout);
  51.      }
  52. }
  53.  
  54. const int MAXN = 105;
  55. const int INF = 1e9;
  56.  
  57. int n;
  58. int a[MAXN];
  59.  
  60. int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
  61. int fact_mask[65];
  62.  
  63. int dp[2][65536];
  64. int head[65537];
  65. int valid_v[3801100];
  66. int valid_nmask[3801100];
  67.  
  68. int active[2][65536];
  69. int n_active[2];
  70. int vis[65536];
  71.  
  72. void nhap(){
  73.     cin >> n;
  74.     for(int i = 1; i <= n; i++){
  75.         cin >> a[i];
  76.     }
  77. }
  78.  
  79. void precompute_transitions() {
  80.     static bool done = false;
  81.     if (done) return;
  82.     done = true;
  83.  
  84.     for(int v = 1; v <= 58; v++){
  85.         fact_mask[v] = 0;
  86.         for(int j = 0; j < 16; j++){
  87.             if(v % p[j] == 0){
  88.                 fact_mask[v] |= (1 << j);
  89.             }
  90.         }
  91.     }
  92.  
  93.     int ptr = 0;
  94.     int total_masks = 1 << 16;
  95.     for(int mask = 0; mask < total_masks; mask++){
  96.         head[mask] = ptr;
  97.         for(int v = 1; v <= 58; v++){
  98.             if((mask & fact_mask[v]) == 0){
  99.                 valid_v[ptr] = v;
  100.                 valid_nmask[ptr] = mask | fact_mask[v];
  101.                 ptr++;
  102.             }
  103.         }
  104.     }
  105.     head[total_masks] = ptr;
  106. }
  107.  
  108. void solve(){
  109.     precompute_transitions();
  110.     memset(vis, 0, sizeof(vis));
  111.  
  112.     active[0][0] = 0;
  113.     n_active[0] = 1;
  114.     dp[0][0] = 0;
  115.  
  116.     for(int i = 1; i <= n; i++){
  117.         int cur = i & 1;
  118.         int pre = cur ^ 1;
  119.         n_active[cur] = 0;
  120.  
  121.         for(int k = 0; k < n_active[pre]; k++){
  122.             int mask = active[pre][k];
  123.             int cost_base = dp[pre][mask];
  124.  
  125.             int start = head[mask];
  126.             int end = head[mask + 1];
  127.             for(int j = start; j < end; j++){
  128.                 int nmask = valid_nmask[j];
  129.                 int cost = cost_base + abs(a[i] - valid_v[j]);
  130.  
  131.                 if(vis[nmask] != i){
  132.                     vis[nmask] = i;
  133.                     dp[cur][nmask] = cost;
  134.                     active[cur][n_active[cur]++] = nmask;
  135.                 } else if(cost < dp[cur][nmask]){
  136.                     dp[cur][nmask] = cost;
  137.                 }
  138.             }
  139.         }
  140.     }
  141.  
  142.     int ans = INF;
  143.     int final_state = n & 1;
  144.     for(int k = 0; k < n_active[final_state]; k++){
  145.         int mask = active[final_state][k];
  146.         if(dp[final_state][mask] < ans){
  147.             ans = dp[final_state][mask];
  148.         }
  149.     }
  150.  
  151.     cout << ans << "\n";
  152. }
  153.  
  154. int main(){
  155.     fastio(); home(); int t = 1;
  156.     //cin >> t;
  157.     while(t--) nhap(), solve();
  158.     return 0;
  159. }
Success #stdin #stdout 0.02s 21564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/U7AnFj
language:
C++14 (gcc 8.3)
created:
12 hours 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!