Advertisement
Fshl0

meh

Jan 17th, 2022
960
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. //#define mp make_pair
  5. #define pb push_back
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9.  
  10. const int MOD = 1e9 + 7;
  11. const int N = 1e5 + 9;
  12. const int INF = 1e9 + 5;
  13. const int K = 55;
  14.  
  15. int segTree[N][K], lazy[N][K], A[N], lp[N], last[N], dp[N][K];
  16.  
  17. void propaGate (int v, int l, int r, int ID) {
  18.     segTree[v][ID] += lazy[v][ID];
  19.    
  20.     if (l == r) {
  21.         lazy[v][ID] = 0;
  22.        
  23.         return;
  24.     }
  25.    
  26.     lazy[2 * v][ID] += lazy[v][ID];
  27.     lazy[2 * v + 1][ID] += lazy[v][ID];
  28.    
  29.     lazy[v][ID] = 0;
  30.     return;
  31. }
  32.  
  33. int getQuery (int v, int l, int r, int L, int R, int ID) {
  34.     propaGate (v, l, r, ID);
  35.    
  36.     if (L <= l && r <= R)
  37.         return segTree[v][ID];
  38.    
  39.     if (l > R || r < L)
  40.         return 0;
  41.        
  42.        
  43.     int mid = (l + r) / 2;
  44.     int Q1 = getQuery (2 * v, l, mid, L, R, ID);
  45.     int Q2 = getQuery (2 * v + 1, mid + 1, r, L, R, ID);
  46.    
  47.     return max (Q1, Q2);
  48. }
  49.  
  50. void updateValue (int v, int l, int r, int idx, int val, int ID) {
  51.     propaGate (v, l, r, ID);
  52.    
  53.     if (l == r) {
  54.         segTree[v][ID] = val;
  55.        
  56.         return;
  57.     }
  58.    
  59.     int mid = (l + r) / 2;
  60.     if (idx <= mid)
  61.         updateValue (2 * v, l, mid, idx, val, ID);
  62.     else updateValue (2 * v + 1, mid + 1, r, idx, val, ID);
  63.    
  64.     segTree[v][ID] = max (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
  65.     return;
  66. }
  67.  
  68. void updateRange (int v, int l, int r, int L, int R, int ID) {
  69.     propaGate (v, l, r, ID);
  70.    
  71.     if (L <= l && r <= R) {
  72.         lazy[v][ID]++;
  73.         propaGate (v, l, r, ID);
  74.        
  75.         return;
  76.     }
  77.    
  78.     if (l > R || r < L)
  79.         return;
  80.        
  81.     int mid = (l + r) / 2;
  82.     updateRange (2 * v, l, mid, L, R, ID);
  83.     updateRange (2 * v + 1, mid + 1, r, L, R, ID);
  84.    
  85.     segTree[v][ID] = max (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
  86.     return;
  87. }
  88.  
  89. vector <int> F (int x) {
  90.     vector <int> v, tmp;
  91.    
  92.     while (lp[x] != x) {
  93.         tmp.pb (lp[x]);
  94.         x /= lp[x];
  95.     }
  96.    
  97.     if (x != 1)
  98.         tmp.pb (lp[x]);
  99.    
  100.     sort (tmp.begin(), tmp.end());
  101.     for (int i = 0; i < (int) tmp.size(); i++) {
  102.         if (i == 0) {
  103.             v.pb (tmp[i]);
  104.            
  105.             continue;
  106.         }
  107.        
  108.         if (tmp[i] != tmp[i - 1])
  109.             v.pb (tmp[i]);
  110.     }
  111.    
  112.     return v;
  113. }
  114.  
  115. int main () {
  116.     int n, k;
  117.     cin >> n >> k;
  118.    
  119.     for (int i = 1; i <= n; i++)
  120.         cin >> A[i];
  121.    
  122.     for (int i = 1; i < N; i++)
  123.         lp[i] = i;
  124.     for (int i = 2; i < N; i++)
  125.         if (lp[i] == i)
  126.             for (int j = i + i; j < N; j += i)
  127.                 lp[j] = i;
  128.    
  129.    
  130.     for (int i = 1; i <= n; i++) {
  131.         for (int j = 1; j <= k + 1; j++) {
  132.             vector <int> v = F (A[i]);
  133.             for (auto u: v) {
  134.                 updateRange (1, 1, n, last[u] + 1, i, j - 1);
  135.                 last[u] = i;
  136.             }
  137.            
  138.             dp[i][j] = getQuery (1, 1, n, 1, i - 1, j - 1);
  139.             updateValue (1, 1, n, i, dp[i][j], j);
  140.         }
  141.     }
  142.    
  143.     cout << dp[n][k + 1] << "\n";
  144.    
  145.     return 0;
  146. }
  147.  
  148.  
  149.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement