oj.uz

Submission #785779

# Submission time Handle Problem Language Result Execution time Memory
785779 2023-07-17T15:17:36 Z jakobrs Hiring (IOI09_hiring) C++17
12 / 100
 1500 ms 13520 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 0 ms 212 KB Partially correct
3 Correct 0 ms 212 KB Output is correct
4 Partially correct 1 ms 212 KB Partially correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 6 ms 340 KB Output isn't correct
7 Incorrect 10 ms 308 KB Output isn't correct
8 Partially correct 15 ms 468 KB Partially correct
9 Incorrect 36 ms 596 KB Output isn't correct
10 Incorrect 42 ms 596 KB Output isn't correct
11 Incorrect 58 ms 636 KB Output isn't correct
12 Incorrect 179 ms 860 KB Output isn't correct
13 Incorrect 123 ms 916 KB Output isn't correct
14 Incorrect 333 ms 916 KB Output isn't correct
15 Incorrect 523 ms 924 KB Output isn't correct

Subtask #2
6.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Partially correct 1 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 957 ms 1360 KB Output isn't correct
5 Execution timed out 1584 ms 4068 KB Time limit exceeded
6 Execution timed out 1537 ms 13484 KB Time limit exceeded
7 Execution timed out 1546 ms 13516 KB Time limit exceeded

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1549 ms 4028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 7212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1536 ms 13520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1545 ms 13208 KB Time limit exceeded
2 Halted 0 ms 0 KB -