Submission #1176341

#TimeUsernameProblemLanguageResultExecution timeMemory
1176341avighnaTwo Dishes (JOI19_dishes)C++20
5 / 100
85 ms15944 KiB
#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m;
  std::cin >> n >> m;
  std::vector<ll> a(n), s(n), p(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i] >> s[i] >> p[i];
  }
  std::vector<ll> b(m), t(m), q(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i] >> t[i] >> q[i];
  }

  std::vector<ll> p_a(n), p_b(m), p_p(n), p_q(m);
  std::partial_sum(a.begin(), a.end(), p_a.begin());
  std::partial_sum(b.begin(), b.end(), p_b.begin());
  std::partial_sum(p.begin(), p.end(), p_p.begin());
  std::partial_sum(q.begin(), q.end(), p_q.begin());

  ll ans = 0;
  ll max_wt = s[0];
  for (int i = 0; i <= n; ++i) {
    ll wt_a = i == 0 ? 0 : p_a[i - 1];
    if (wt_a > max_wt) {
      continue;
    }
    int idxb = std::upper_bound(p_b.begin(), p_b.end(), max_wt - wt_a) -
               p_b.begin() - 1;
    ans =
        std::max(ans, (i == 0 ? 0 : p_p[i - 1]) + (idxb >= 0 ? p_q[idxb] : 0));
  }
  std::cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...