Submission #752111

#	Time	Username	Problem	Language	Result	Execution time	Memory
752111		DJeniUp	Hiring (IOI09_hiring)	C++17	100 / 100	716 ms	59120 KiB

hiring

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
//#define MOD 998244353
#define INF 1000007
#define eps 0.0000000001

ll n;

ld k,a[5*N],b[5*N],sm[2*N];

struct D{
    ll n;
    
    ld a,b;
}d[5*N];

bool mcp(D d1, D d2){
    if(d1.a*d2.b!=d2.a*d1.b)return d1.a*d2.b<d2.a*d1.b;
    else return d1.b<d2.b;
}

bool mcp1(D d1, D d2){
    return d1.n<d2.n;
}

priority_queue<pairld>q;

priority_queue<ll,vector<ll>, greater<ll> >rs;

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        d[i].n=i;
        d[i].a=a[i];
        d[i].b=b[i];
    }
    sort(d+1,d+1+n,mcp);
    ll res=0;
    ld x=0;
    ld y=0;
    ll h=0;
    ll j=0;
    for(int i=1;i<=n;i++){
        x=max(x,d[i].a/d[i].b);
        y+=d[i].b;
        q.push({d[i].b,d[i].n});
        h++;
        while(x*y>k+eps){
            y-=q.top().fr;
            q.pop();
            h--;
        }
        sm[i]=x*y;
        if(h>res+eps){
            res=h;
            j=i;
        }else if(h==res){
            if(sm[j]>x*y+eps){
                j=i;
            }
        }
    }
    //cout<<j<<" "<<res<<endl;
    while(q.size()>0){
        q.pop();
    }
    x=0;
    y=0;
    for(int i=1;i<=j;i++){
        x=max(x,d[i].a/d[i].b);
        y+=d[i].b;
        q.push({d[i].b,d[i].n});
        while(x*y>k){
            y-=q.top().fr;
            q.pop();
        }
        
    }
    while(q.size()>0){
        rs.push(q.top().sc);
        q.pop();
    }
    cout<<rs.size()<<endl;
    while(rs.size()>0){
        cout<<rs.top()<<endl;
        rs.pop();
    }

    return 0;
}

• 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