Subtask 1: Chúng ta đơn giản là chọn ~2^d~ khả năng có thể, với mỗi khả năng chúng ta for qua các thao tác và update trâu.

Độ phức tạp: ~O(n \cdot 2^d \cdot d)~.

Subtask 2:

Để làm được subtask này cũng như các subtask sau, ta có nhận xét như sau:

• Giả sử dãy ~a[\ ]~ chỉ đang bao gồm các số bằng nhau (điều kiện này cũng sẽ thỏa mãn ngay sau lần đầu tiên chúng ta sử dụng thao tác loại ~2~).

• Gọi ~c[\ ]~ là dãy thỏa mãn ~c[i] = a[i] - i \space \forall \space 1 \le i \le n~.

• Dễ dàng thấy rằng hiện tại dãy ~c[]~ đang giảm nghiêm ngặt (~c[i] > c[i + 1] \space \forall \space 1 \le i < n~).

• Ở mỗi bước, ta đều chỉ update một prefix của ~a~, tức là cũng update một prefix của ~c~ lên ~1~. Điều này có nghĩa là ~\forall 1 \le i < n~, nếu chúng ta update số ~c[i + 1]~ lên ~1~ thì cũng phải update ~c[i]~ lên ~1~, trong khi điều ngược lại chưa chắc đã đúng. Do đó dãy ~c[\ ]~ sẽ luôn luôn giảm nghiêm ngặt.

• Mỗi lần thao tác ~2~ được sử dụng, chúng ta cần đếm số lượng vị trí ~i~ thỏa mãn ~a[i] = i~, hay ~c[i] = 0~. Do dãy ~b[\ ]~ giảm ngặt, điểm số sẽ chỉ được cộng thêm tối đa là ~1~. Ngoài ra sau khi thao tác ~2~ được sử dụng, thao tác ~1~ tiếp theo sẽ luôn luôn update ~a[1]~ lên ~1~, và điểm số khi đó đã là ~1~.

Kết luận sau những nhận xét trên: sau lần đầu dùng thao tác ~2~, việc dùng so le ~2~ thao tác ~1~ và ~2~ mà không cần quan tâm đến ~b[i]~ là tối ưu.

Ở subtask ~2~, vì các số đã bằng nhau sẵn, nên có ~2~ trường hợp:

• Các số đang bằng ~0~. Ta cần thực hiện thao tác ~1~ trước rồi đến ~2~, và đáp số là ~\frac{d}{2}~.

• Các số đang khác ~0~. Vì các số ~\le n~ nên ta thực hiện luôn thao tác ~2~ trước, và đáp số là ~\frac{d + 1}{2}~.

Subtask 3:

Ta thấy rằng thứ duy nhất quan trọng ở đây là khi nào thao tác ~2~ được sử dụng lần đầu tiên (trước đó chúng ta sử dụng thao tác ~1~ liên tục, còn sau đó chúng ta so le giữa hai loại thao tác).

Ngoài ra việc sử dụng thao tác ~2~ sau vị trí thứ ~2 \cdot n~ là không tối ưu, vì thay vì làm như vậy ta có thể ngay lập tức áp dụng chiến thuật sole từ đầu (bạn đọc tự chứng minh)

Ta sẽ for qua vị trí đầu tiên mà thao tác ~2~ được sử dụng và update các vị trí tương ứng.

Độ phức tạp: ~O(n^2)~ (vì ta chỉ for qua ~O(n)~ vị trí).

Subtask 4:

Ta cần maintain mảng ~c[\ ]~ như đã nói ở subtask ~2~ và thực hiện ~2~ thao tác sau:

• Update đoạn ~[1, i]~ lên ~1~;

• Đếm số số ~c[i] = 0~.

Thay vì đếm số lần xuất hiện của ~0~ trong dãy — một việc không đơn giản, chúng ta có nhận xét sau: Khi một vị trí ~c[i] > 0~, vị trí đó sẽ không ảnh hưởng đến đáp án nữa (vì chỉ có thao tác tăng).

Với những số như vậy, ta đặt lại ~c[i] = -\infty~ (lưu ý ~\infty~ ở đây chỉ cần để khoảng ~10^9~ là được). Khi đó, ~0~ sẽ là giá trị lớn nhất, và bài toán trở thành lưu số lớn nhất trong dãy cũng như số lần xuất hiện của số đó, và đây là bài Segment Tree cơ bản.

ĐPT: ~O(n \cdot \log_2(n))~.

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

int n, k, d;
int a[N], v[N], tol[N];

ii IT[N << 2];
int laz[N << 2];

void merge(int id){
    IT[id].fi = max(IT[id << 1].fi, IT[id << 1 | 1].fi);
    IT[id].se = 0;
    IT[id].se += IT[id << 1].se * (IT[id].fi == IT[id << 1].fi);
    IT[id].se += IT[id << 1 | 1].se * (IT[id].fi == IT[id << 1 | 1].fi);
}

void build(int id, int l, int r){
    if(l == r){
        IT[id] = {a[l] - l, 1};
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    merge(id);
}

void lazy(int id){
    int t = laz[id];
    if(!t) return;
    IT[id << 1].fi += t;
    IT[id << 1 | 1].fi += t;
    laz[id << 1] += t;
    laz[id << 1 | 1] += t;
    laz[id] = 0;
}

void upd(int id, int l, int r, int L, int R, int val){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        IT[id].fi += val;
        laz[id] += val;
        return;
    }
    lazy(id);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
    merge(id);
}

int getpos(int id, int l, int r){
    if(l == r) return l;
    int mid = (l + r) >> 1;
    lazy(id);
    if(IT[id << 1].fi == IT[id].fi) return getpos(id << 1, l, mid);
    else return getpos(id << 1 | 1, mid + 1, r);
}



void process(){
    cin >> n >> k >> d;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= k; i++) cin >> v[i];
    build(1, 1, n);
    while(IT[1].fi > 0){
        int pos = getpos(1, 1, n);
        upd(1, 1, n, pos, pos, -1e7);
    }
    // the first harvest operation is in operation i (we know for sure that there must be one)
    ii answer = {0, 0};
    for(int i = 1; i <= min(d, (2 * n) + 5); i++){
        if(i > 1){
            int ind = (i - 1) % k;
            if(!ind) ind = k;
            upd(1, 1, n, 1, v[ind], 1);
            while(IT[1].fi > 0){
                int pos = getpos(1, 1, n);
                upd(1, 1, n, pos, pos, -1e7);
            }
        }
        int total = 0;
        if(IT[1].fi == 0) total = IT[1].se;
        int temp = (d - i) / 2;
        answer = max(answer, {temp + total, -i});
    }
    cout << answer.fi << "\n";
    //cout << -answer.se << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    process();
}