Submission #73492470

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <atcoder/all>
#define DEBUG_PRINT(x) std::cerr << #x << ": " << (x) << std::endl
#define SQUARED(x) ((x) * (x))
#define CUBED(x) ((x) * (x) * (x))
#define CEIL(x, y) ((x + y - 1) / y)
#define FLOOR(x, y) (x / y)
#define CTOI(c) ((c) - '0')
#define CHECK_HW(h, w) (0 <= h and h < H and 0 <= w and w < W)

using namespace std;
using namespace atcoder;

const long long INF = 1e15;
const long double EPS = 1e-8;

int main()
{
  long long T;
  cin >> T;
  for (int ttt = 0; ttt < T; ttt++) {
    long long N, D;
    vector<long long> A, B;
    cin >> N >> D;
    for (int i = 0; i < N; i++) {
      long long a;
      cin >> a;
      A.push_back(a);
    }
    for (int i = 0; i < N; i++) {
      long long b;
      cin >> b;
      B.push_back(b);
    }

    deque<pair<long long, long long>> egg;
    for (int i = 0; i < N; i++) {
      egg.push_back({i, A[i]});
      while (true) {
        auto&& [d, n] = egg.front();
        if (B[i] > n) {
          B[i] -= n;
          egg.pop_front();
        }
        else {
          n -= B[i];
          break;
        }
      }
      while (!egg.empty()) {
        auto&& [d, n] = egg.front();
        if (i - d >= D) {
          egg.pop_front();
        }
        else {
          break;
        }
      }
    }

    long long ans = 0;
    while (!egg.empty()) {
      auto [d, n] = egg.front();
      ans += n;
      egg.pop_front();
    }

    cout << ans << endl;
  }

  return 0;
}

Submission Info

Judge Result