제출 #1337788

#제출 시각아이디문제언어결과실행 시간메모리
1337788maddoxikHiring (IOI09_hiring)C++20
57 / 100
447 ms70892 KiB
#include<bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define ve vector
#define pb push_back
#define en end
#define be begin
#pragma GGC optimize("O3,unroll-loops")
#pragma GGC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ppb pop_back
using namespace std;
bool comp(pair<float,int>a,pair<float,int>b){
  if (a.ff>=b.ff) return 0;
  else return 1;
}
int n;
long long m;
int32_t main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  ve<pair<double,double>>r;
  ve<pair<float,int>>v;
  for (int i=0; i<n; i++){
    int x,y;
    cin>>x>>y;
    double dx=x,dy=y;
    float z=dx/dy;
   // cout<<fixed<<" "<<setprecision(9)<<" "<<dx/dy<<endl;
    r.pb({x,y});
    v.pb({z,i});
  }
  ve<int>z;
  sort(v.be(),v.en(),comp);
  priority_queue<pair<int,int>>qu;
  int sm=0;
  int mx=0;
  ve<int>a[n];
  ve<int>b[n];
  double mxx;
  int t=0;
  for (int i=0; i<n; i++){
    double k=v[i].ff;
    if (qu.size()>0){
      while (sm*k>m) sm-=qu.top().ff,b[i].pb(qu.top().ss),qu.pop();
    }
    if ((sm+r[v[i].ss].ss)*k<=m) {sm+=r[v[i].ss].ss; qu.push({r[v[i].ss].ss,v[i].ss}); a[i].pb(v[i].ss);}
    else if (qu.top().ff>r[v[i].ss].ss) {sm-=qu.top().ff; b[i].pb(qu.top().ss); qu.pop(); qu.push({r[v[i].ss].ss,v[i].ss}); sm+=r[v[i].ss].ss; a[i].pb(v[i].ss);}
    if (mx<qu.size()) mxx=1e18;
    if (mx<qu.size() || (mx==qu.size() && mxx<sm*k)){
      t=i;
    }
    mxx=max(mxx,sm*k);
    mx=max(mx,(int)qu.size());
   // cout<<setprecision(9)<<fixed<<k<<" "<<sm<<endl;
  }
  ve<int>c(n,0);
  for (int i=0; i<=t; i++){
    for (auto g:a[i]){
      c[g]=1;
      //cout<<"a: "<<g<<endl;
    }
    for (auto g:b[i]){
      c[g]=0;
     // cout<<"b: "<<g<<endl;
    }
  }
  cout<<mx<<endl;
  //cout<<t<<endl;
  for (int i=0; i<n; i++){
    if (c[i]==1) cout<<i+1<<endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...