Submission #963060

#	Time	Username	Problem	Language	Result	Execution time	Memory
963060		hirayuu_oj	Hiring (IOI09_hiring)	C++17	50 / 100	377 ms	32564 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
using ld=long double;

template<class S>
struct fw_tree{
    int size;
    vector<S> tree;
    fw_tree(int sz){
        size=sz;
        tree=vector<S>(sz+1,0);
    }
    void add(int p,int v){
        p++;
        while(p<=size){
            tree[p]+=v;
            p+=p&-p;
        }
    }
    S sum(int r){
        S ret=0;
        while(r>0){
            ret+=tree[r];
            r-=r&-r;
        }
        return ret;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    ll W;
    cin>>N>>W;
    vector<pair<int,int>> work(N);
    rep(i,N){
        int S,Q;
        cin>>S>>Q;
        work[i]={Q,S};
    }
    sort(all(work));
    vector<pair<ld,int>> order(N);
    rep(i,N){
        order[i]={((ld)work[i].second)/((ld)work[i].first),i};
    }
    sort(all(order));
    fw_tree<ll> cost(N);
    fw_tree<int> count(N);
    pair<int,ld> ans={-1,0};
    pair<int,int> out={-1,-1};
    rep(i,N){
        ll q,s;
        tie(q,s)=work[order[i].second];
        count.add(order[i].second,1);
        cost.add(order[i].second,q);
        int ok=0,ng=N+1;
        while(ng-ok>1){
            int mid=(ok+ng)>>1;
            if(cost.sum(mid)*s<=W*q){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int now=count.sum(ok);
        ld cst=cost.sum(ok)*order[i].first;
        if(ans<pair(now,-cst)){
            ans=pair(now,-cst);
            out=pair(i,ok);
        }
    }
    cout<<ans.first<<"\n";
    vector<bool> col(N,0);
    rep(i,out.first+1){
        col[order[i].second]=1;
    }
    rep(i,out.second){
        if(col[i]){
            cout<<i+1<<"\n";
        }
    }
}

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