Advertisement
YEZAELP

TOI16: Dino Cell

Nov 26th, 2021
676
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e6 + 10;
  5. const int K = 1e7 + 10;
  6. const int inf = 1e9;
  7. int ar[N], pos[K], neg[K], st[N], dppos[N], dpneg[N];
  8. bool is_fac[K];
  9. int z, k, n;
  10.  
  11. int Sum(int type, int i){
  12.     if(type == 1) return pos[k] * (i / k) + pos[i % k];
  13.     else return neg[k] * (i / k) + neg[i % k];
  14. }
  15.  
  16. int main(){
  17.  
  18.     scanf("%d %d %d", &z, &k, &n);
  19.  
  20.     for(int i=1;i<=n;i++)
  21.         scanf("%d", &ar[i]);
  22.  
  23.     for(int f=2;f<=k;f++){
  24.         if(is_fac[f] or k % f != 0) continue;
  25.         for(int num=f;num<=k;num+=f){
  26.             is_fac[num] = true;
  27.         }
  28.     }
  29.  
  30.     for(int i=1;i<=k;i++){
  31.         if(is_fac[i]) pos[i] = 1;
  32.         else neg[i] = 1;
  33.         pos[i] += pos[i - 1];
  34.         neg[i] += neg[i - 1];
  35.     }
  36.  
  37.     int mx = 0;
  38.     dppos[1] = -inf;
  39.     dpneg[1] = -inf;
  40.     for(int i=2;i<=n;i++){
  41.         int posnc = ( Sum(1, ar[i]) - Sum(1, ar[i-1] - 1) ) - ( Sum(2, ar[i]) - Sum(2, ar[i-1] - 1) );
  42.         int posc = dppos[i - 1] + ( Sum(1, ar[i]) - Sum(1, ar[i-1]) ) - ( Sum(2, ar[i]) - Sum(2, ar[i-1]) );
  43.         dppos[i] = max(posnc, posc);
  44.  
  45.         int negnc = ( Sum(2, ar[i]) - Sum(2, ar[i-1] - 1) ) - ( Sum(1, ar[i]) - Sum(1, ar[i-1] - 1) );
  46.         int negc = dpneg[i - 1] + ( Sum(2, ar[i]) - Sum(2, ar[i-1]) ) - ( Sum(1, ar[i]) - Sum(1, ar[i-1]) );
  47.         dpneg[i] = max(negnc, negc);
  48.  
  49.         mx = max({ mx , dppos[i] , dpneg[i] });
  50.     }
  51.  
  52.     printf("%d", mx);
  53.  
  54.     return 0;
  55. }
Advertisement
RAW Paste Data Copied
Advertisement