Submission #785779

#	Time	Username	Problem	Language	Result	Execution time	Memory
785779		jakobrs	Hiring (IOI09_hiring)	C++17	12 / 100	1584 ms	13520 KiB

hiring

#include <iostream>
#include <algorithm>
#include <vector>

using i64 = int64_t;
using f64 = double;

struct Candidate {
  i64 id;
  i64 s;
  i64 q;
};

int main() {
  i64 n, w;
  std::cin >> n >> w;

  std::vector<Candidate> candidates;
  for (i64 i = 0; i < n; i++) {
    i64 s, q;
    std::cin >> s >> q;
    candidates.push_back({ .id = i, .s = s, .q = q });
  }

  std::sort(candidates.begin(), candidates.end(), [](const auto &lhs, const auto &rhs) {
    return lhs.s * rhs.q < rhs.s * lhs.q;
  });
  std::vector<i64> best_bin;
  double best_budget = -1;
  for (i64 i = 0; i < n; i++) {
    auto model = candidates[i];
    auto s_over_q = (f64)model.s / (f64)model.q;

    double budget = w;

    std::vector<i64> bin;
    for (i64 j = 0; j < n; j++) {
      const auto &candidate = candidates[j];
      double price = s_over_q * candidate.q;
      if (price + 0.000001 >= candidate.s && price <= budget) {
        budget -= price;
        bin.push_back(j);
      }
    }

    if (bin.size() > best_bin.size() || (bin.size() == best_bin.size() && budget > best_budget)) {
      best_bin = std::move(bin);
      best_budget = budget;
    }
  }

  std::cout << best_bin.size() << '\n';
  for (i64 x : best_bin)
    std::cout << candidates[x].id + 1 << '\n';
}

• Subtask 1: 6 / 30
• Subtask 2: 6 / 28
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6