Submission #907573

#	Time	Username	Problem	Language	Result	Execution time	Memory
907573		Mathias	Hiring (IOI09_hiring)	C++14	100 / 100	755 ms	46344 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int MAXN = 5e5+7;
const ll INF = 1e18;
ll m[MAXN];
ll q[MAXN];
pair<ld,ll> t[MAXN];
multiset<pair<ld,ll> >s;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll suma=0,res=0,n,b;
	pair<ld,ll> p;
	ld mini=INF;
	ld st,x;
	cin>>n>>b;
	for(int i=1;i<=n;i++){
		cin>>m[i]>>q[i];
		st=(ld)m[i]/(ld)q[i];
		t[i]={st,i};
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		s.insert({-q[t[i].second],t[i].second});
		suma+=q[t[i].second];
		x=t[i].first;
		while(1){
			if((ld)suma*x<=(ld)b) break;
			p=*s.begin();
			suma+=p.first;
			s.erase(s.begin());
		}
		if(s.size()>res){
			res=s.size();
			mini=suma*x;
		}
		else if(s.size()==res){
			mini=min(mini,(ld)suma*x);
		}
	}
	s.clear(); suma=0;
	for(int i=1;i<=n;i++){
		s.insert({-q[t[i].second],t[i].second});
		suma+=q[t[i].second];
		x=t[i].first;
		while(1){
			if((ld)suma*x<=(ld)b) break;
			p=*s.begin();
			suma+=p.first;
			s.erase(s.begin());
		}
		if(s.size()==res and mini==(ld)suma*x){
			break;
		}
	}
	cout<<res<<'\n';
	for(auto xd:s){
		cout<<xd.second<<'\n';
	}
	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:34:14: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |   if(s.size()>res){
      |      ~~~~~~~~^~~~
hiring.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |   else if(s.size()==res){
      |           ~~~~~~~~^~~~~
hiring.cpp:53:14: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   53 |   if(s.size()==res and mini==(ld)suma*x){
      |      ~~~~~~~~^~~~~

• 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