Restaurants

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int INF = 0x3f3f3f3f; //❄️
    5int main() {
    6    ios::sync_with_stdio(0); cin.tie(0); 
    7    int n, t, k, v; cin >> n >> t >> k >> v;
    8    vector<bool> pos(n + 1);
    9    for (int i = 0; i < v; i++) {
    10        int c; cin >> c;
    11        pos[c] = 1;
    12    }
    13    int ans = 0, cnt = 0;
    14    for (int i = 1; i <= t; i++) {
    15        if (pos[i]) cnt++;
    16    }
    17    if (cnt < k) {
    18        for (int i = t; i >= 1; i--) {
    19            if(pos[i]) continue;
    20            else pos[i] = 1;
    21            cnt++;
    22            ans++;
    23            if(!(cnt < k)) break;
    24        }
    25    }
    26    for (int i = 2; i <= n; i++) {
    27        if(i + t - 1 > n) break;
    28        if(pos[i - 1]) cnt--;
    29        if(pos[i + t - 1]) cnt++;
    30        if(cnt < k) {
    31            for (int j = i + t - 1; j >= i; j--) {
    32                if(pos[j]) continue;
    33                else pos[j] = 1;
    34                cnt++;
    35                ans++;
    36                if(!(cnt < k)) break;
    37            }
    38        }
    39    }
    40    cout << ans << '\n';
    41    return 0;
    42}