제출 #979875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979875		Glauco	Hiring (IOI09_hiring)	C++17	100 / 100	388 ms	22916 KiB

hiring

#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 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6