Submission #220795

#	Time	Username	Problem	Language	Result	Execution time	Memory
220795		tatyam	Hiring (IOI09_hiring)	C++17	100 / 100	348 ms	26892 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)


ll cnt;
vector<ll> hist;
struct Q{
    priority_queue<pll> q;
    ll sum = 0;
    void push(ll val, ll index){
        cnt++;
        sum += val;
        hist.push_back(index);
        q.emplace(val, index);
    }
    void pop(){
        cnt--;
        sum -= q.top().first;
        hist.push_back(q.top().second);
        q.pop();
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, w;
    cin >> n >> w;
    vector<pll> a(n);
    each(i, a) cin >> i.first >> i.second;
    vector<ll> b(n);
    iota(all(b), 0);
    sort(all(b), [&](ll x, ll y){ return a[x].first * a[y].second < a[x].second * a[y].first; });
    ld rate = 0, cost = 0;
    ll ans = 0;
    Q q;
    vector<bool> hire(n);
    auto update = [&](ld cost_) -> void {
        if(ans > cnt) return;
        if(ans == cnt && cost <= cost_) return;
        ans = cnt;
        cost = cost_;
        each(i, hist) hire[i] = !hire[i];
        hist.clear();
    };
    each(i, b){
        auto [sal, qual] = a[i];
        rate = ld(sal) / qual;
        q.push(qual, i);
        while(q.sum * rate > w) q.pop();
        update(q.sum * rate);
    }
    cout << ans << '\n';
    rep(n) if(hire[i]) cout << i + 1 << '\n';
}

• 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