Submission #68153658

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)

#if __has_include("shik/dump.h")
#include "shik/dump.h"
#else
#define dump(...) 0
#endif

using namespace std;

const int N = 10010;
const int M = 5e5 + 10;

int n, m, p[N], a[N], b[N];
int qs[M];
void input() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> p[i] >> a[i] >> b[i];
  cin >> m;
  for (int i = 0; i < m; i++) cin >> qs[i];
}

const int K = 510;
int dp[N][K];

int go(int pos, int mood) {
  if (mood < 0) mood = 0;
  if (pos == n) return mood;
  if (mood < K && dp[pos][mood] != -1) return dp[pos][mood];
  int d = p[pos] >= mood ? a[pos] : -b[pos];
  int ans = go(pos + 1, mood + d);
  if (mood < K) dp[pos][mood] = ans;
  return ans;
}

int sb[N];
int solve(int q) {
  int lo = 0, hi = n;
  while (lo != hi) {
    int mid = (lo + hi) >> 1;
    if (q - sb[mid] > 500) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  int mood = q - sb[lo];
  int ans = go(lo, mood);
  return ans;
}

void solve() {
  for (int i = 0; i < n; i++) sb[i + 1] = sb[i] + b[i];
  memset(dp, -1, sizeof(dp));
  for (int i = 0; i < m; i++) {
    int ans = solve(qs[i]);
    cout << ans << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  return 0;
}

Submission Info

Judge Result