Submission

Score: 100

User: Kittiponn

Problemset: Red Zone

Language: cpp

Time: 0.021 second

Submitted On: 2026-03-05 11:08:53

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

#define ll long long
const int nx = 1e5+5;

ll n, m, l, d;
ll bo[nx], ho[nx], pr[nx], da[nx];

int solve(int md) {
    // 1. Reset arrays
    for(int i = 0; i <= n + 1; i++) pr[i] = 0, da[i] = 0;

    // 2. Difference Array Update
    for(int i = 0; i < md; i++) {
        // ปรับตำแหน่งระเบิดเป็น 0-based
        ll center = bo[i] - 1; 
        ll left = max(0LL, center - l);
        ll right = min(n - 1, center + l);
        
        pr[left] += d;
        if(right + 1 < n) pr[right + 1] -= d;
    }

    // 3. Prefix Sum
    da[0] = pr[0];
    for(int i = 1; i < n; i++) {
        da[i] = da[i - 1] + pr[i];
    }

    // 4. Check results
    for(int i = 0; i < n; i++) {
        if(ho[i] > da[i]) return 0; // เลือดยังเหลือ = ไม่ผ่าน
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    if(!(cin >> n >> m >> l >> d)) return 0;
    for(int i = 0; i < n; i++) cin >> ho[i];
    for(int i = 0; i < m; i++) cin >> bo[i];

    int li = 0, r = m + 1;
    while(li < r) {
        int md = li + (r - li) / 2;
        if(solve(md)) r = md;
        else li = md + 1;
    }

    if(li == m + 1) cout << "-1";
    else cout << li;

    return 0;
}