Submission

Score: 100

User: kavin8888

Problemset: Red Zone

Language: cpp

Time: 0.019 second

Submitted On: 2025-11-07 21:46:17

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<long long int>
#define ll long long
int chouse,cbomb,rbomb;
ll dbomb;
vi house;
vll bomb;
bool chk(int x) {
	static vector<int> res;
	res.assign(chouse+3,0);
	for(int i=0;i<x;i++) {
		int pos=bomb[i];
		int l=max(1,pos-rbomb);
		int r=min(chouse,pos+rbomb);
		res[l]++;
		res[r+1]--;
	}
	ll vip=0;
	for(int i=1;i<=chouse;i++) {
		vip+=res[i];
		ll vep=(house[i-1]+dbomb-1)/dbomb;
		if(vip<vep) return false;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>chouse>>cbomb>>rbomb>>dbomb;
	for(int i=0;i<chouse;i++) {
		int a;
		cin>>a;
		house.push_back(a);
	}
	for(int i=0;i<cbomb;i++) {
		int b;
		cin>>b;
		bomb.push_back(b);
	}
	int l=1,r=cbomb,ans=-1;
	while(l<=r) {
		int mid=(l+r)/2;
		if(chk(mid)) {
			ans=mid;
			r=mid-1;
		}
		else {
			l=mid+1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}