Submission #312686

#	Time	Username	Problem	Language	Result	Execution time	Memory
312686		joseacaz	Hiring (IOI09_hiring)	C++17	53 / 100	1600 ms	21576 KiB

hiring

#include <iostream>
#include <algorithm>
#include <vector>
#define MAXN 500005

using namespace std;
typedef long long lld;

struct Workers
{
	lld ind;
	double s, q;
};

lld N, W, amount_w, max_w;
double price_q, tot_s, max_s, prices[MAXN];
Workers worker[MAXN];
vector < lld > list, workerList;

bool cmp ( Workers _a, Workers _b )
{
	if ( _a.q == _b.q )
		return _a.s < _b.s;
	return _a.q < _b.q;
}

int main ()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> W;
	for ( lld i = 0; i < N; i++ )
		cin >> worker[i].s >> worker[i].q, worker[i].ind = i + 1;
	
	sort ( worker, worker + N, cmp );

	for ( lld i = 0; i < N; i++ )
		prices[i] = worker[i].s / worker[i].q;
	
	sort ( prices, prices + N );
	
	for ( lld i = 0; i < N; i++ )
	{
		if ( i > 0 && prices[i] == prices[i - 1] )
			continue;
		price_q = prices[i];
		amount_w = 0;
		tot_s = 0;
		workerList.clear();
		for ( lld j = 0; j < N; j++ )
			if ( price_q * worker[j].q >= worker[j].s && tot_s + (price_q * worker[j].q) <= W )
				amount_w++, tot_s += price_q * worker[j].q, workerList.push_back(worker[j].ind);

		if ( amount_w > max_w )
		{
			max_w = amount_w;
			max_s = tot_s;
			list = workerList;
		}
		else if ( amount_w == max_w && tot_s < max_s )
		{
			tot_s = max_s;
			list = workerList;
		}
	}
	
	cout << max_w << "\n";
	for ( lld i = 0; i < list.size(); i++ )
		cout << list[i] << "\n";
	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:67:21: warning: comparison of integer expressions of different signedness: 'lld' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for ( lld i = 0; i < list.size(); i++ )
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 26 / 30
• Subtask 2: 18 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6