Submission #1176341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176341		avighna	Two Dishes (JOI19_dishes)	C++20	5 / 100	85 ms	15944 KiB

dishes

#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';
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9