oj.uz

Submission #979876

# Submission time Handle Problem Language Result Execution time Memory
979876 2024-05-11T14:26:37 Z Glauco Hiring (IOI09_hiring) C++17
100 / 100
 273 ms 17076 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n; long long b;
  cin >> n >> b;

  vector<int> s(n), q(n);
  for(int i = 0; i < n; i++) cin >> s[i] >> q[i];

  vector<pair<double, pair<int, int>>> ratio(n);
  for(int i = 0; i < n; i++) ratio[i] = {(s[i]*1.0)/(q[i]*1.0), {q[i], i}};
  sort(ratio.begin(), ratio.end());

  auto calc = [&](pair<int, double> target) {
    long long tot = 0;
    priority_queue<pair<int, int>> pq;
    pair<int, double> best = {0, -1e9};

    for(int i = 0; i < n; i++){
      pq.push(ratio[i].second); tot += ratio[i].second.first;

      while(tot*1.0*ratio[i].first > b){
        tot -= pq.top().first;
        pq.pop();
      }

      best = max(best, {pq.size(), -tot*1.0*ratio[i].first});

      if(best == target){
        cout << best.first << '\n';
        while(!pq.empty()){
          cout << pq.top().second+1 << '\n';
          pq.pop();
        }
        return best;
      }
    }

    return best;
  };

  calc(calc({-1, -1}));
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 6 ms 860 KB Output is correct
15 Correct 6 ms 824 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 860 KB Output is correct
5 Correct 21 ms 2300 KB Output is correct
6 Correct 142 ms 10200 KB Output is correct
7 Correct 199 ms 14892 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 484 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3992 KB Output is correct
2 Correct 51 ms 4016 KB Output is correct
3 Correct 53 ms 4292 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7080 KB Output is correct
2 Correct 85 ms 7080 KB Output is correct
3 Correct 85 ms 6984 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 15324 KB Output is correct
2 Correct 218 ms 15372 KB Output is correct
3 Correct 214 ms 15248 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 17008 KB Output is correct
2 Correct 247 ms 17064 KB Output is correct
3 Correct 273 ms 17076 KB Output is correct