TOI16: Dino Cell

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
const int K = 1e7 + 10;
const int inf = 1e9;
int ar[N], pos[K], neg[K], st[N], dppos[N], dpneg[N];
bool is_fac[K];
int z, k, n;

int Sum(int type, int i){
    if(type == 1) return pos[k] * (i / k) + pos[i % k];
    else return neg[k] * (i / k) + neg[i % k];
}

int main(){

    scanf("%d %d %d", &z, &k, &n);

    for(int i=1;i<=n;i++)
        scanf("%d", &ar[i]);

    for(int f=2;f<=k;f++){
        if(is_fac[f] or k % f != 0) continue;
        for(int num=f;num<=k;num+=f){
            is_fac[num] = true;
        }
    }

    for(int i=1;i<=k;i++){
        if(is_fac[i]) pos[i] = 1;
        else neg[i] = 1;
        pos[i] += pos[i - 1];
        neg[i] += neg[i - 1];
    }

    int mx = 0;
    dppos[1] = -inf;
    dpneg[1] = -inf;
    for(int i=2;i<=n;i++){
        int posnc = ( Sum(1, ar[i]) - Sum(1, ar[i-1] - 1) ) - ( Sum(2, ar[i]) - Sum(2, ar[i-1] - 1) );
        int posc = dppos[i - 1] + ( Sum(1, ar[i]) - Sum(1, ar[i-1]) ) - ( Sum(2, ar[i]) - Sum(2, ar[i-1]) );
        dppos[i] = max(posnc, posc);

        int negnc = ( Sum(2, ar[i]) - Sum(2, ar[i-1] - 1) ) - ( Sum(1, ar[i]) - Sum(1, ar[i-1] - 1) );
        int negc = dpneg[i - 1] + ( Sum(2, ar[i]) - Sum(2, ar[i-1]) ) - ( Sum(1, ar[i]) - Sum(1, ar[i-1]) );
        dpneg[i] = max(negnc, negc);

        mx = max({ mx , dppos[i] , dpneg[i] });
    }

    printf("%d", mx);

    return 0;
}