Submission

Score: 100

User: kittipos

Problemset: Red Zone

Language: cpp

Time: 0.027 second

Submitted On: 2026-03-13 10:36:50

#include <bits/stdc++.h>

using namespace std;

int n, m, l, d;
int check(int step, const vector<int> house, const vector<int> targets) {
  // cout << "checkpoint 2" << endl;
  vector<int> diffrent;
  int prev = 0;
  diffrent.resize(n + 1);
  for (int i = 0; i < n; i++) {
    diffrent[i] = house[i] - prev;
    prev = house[i];
  }

  for (int i = 0; i < step; i++) {
    int start = max(0, targets[i] - l);
    int end = min(n, targets[i] + l + 1);
    diffrent[start] -= d;
    diffrent[end] += d;
  }
  // cout << "checkpoint 4" << endl;

  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += diffrent[i];
    if (sum > 0) {
      return false;
    }
  }
  return true;
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m >> l >> d;

  vector<int> house;
  house.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> house[i];
  }
  vector<int> targets;
  targets.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> targets[i];
    targets[i]--;
  }

  if (!check(m, house, targets)) {
    cout << "-1\n";
    return 0;
  }

  int left = 0;
  int right = m + 1;

  while (left + 1 < right) {
    // cout << "checkpoint 1, left: " << left << ", right: " << right << endl;
    int center = (left + right) / 2;
    if (check(center, house, targets)) {
      right = center;
    } else {
      left = center;
    }
  }

  cout << left + 1;

  return 0;
}