Submission

Score: 100

User: syndrxme

Problemset: Red Zone

Language: cpp

Time: 0.054 second

Submitted On: 2026-03-14 14:20:45

#include<bits/stdc++.h>
using namespace std;
int n,m,l,d;
vector<int> house;
vector<int> bomb;

bool check(int mid){
    vector<long long> diff(n+2,0);
    for(int i=1;i<=mid;i++){
        int pos = bomb[i];
        int left = max(1,pos-l);
        int right = min(n,pos+l);
        diff[left]+=d;
        diff[right+1]-=d;
    }
    long long curdamage = 0;
    for(int i=1;i<=n;i++){
        curdamage+=diff[i];
        if(curdamage<house[i]){
            return false;
        }
    }
    return true;
}

int main(){
    
    cin>>n>>m>>l>>d;
    house.resize(n + 1);
    bomb.resize(m + 1);
    for(int i=1;i<=n;i++){
        cin>>house[i];
    }
    for(int i=1;i<=m;i++){
        cin>>bomb[i];
    }
    int left=0;
    int r=m;
    int ans=-1;
    while(left<=r){
        int mid = left + (r-left)/2;
        if(check(mid)==true){
            ans = mid;
            r=mid-1;
        }else{
            left=mid+1;
        }
    }
    cout<<ans;
    return 0;
}