Submission #328749

#	Time	Username	Problem	Language	Result	Execution time	Memory
328749		luciocf	Hiring (IOI09_hiring)	C++14	38 / 100	1596 ms	6464 KiB

hiring

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 5e5+10;

int n;
ll w;

struct S
{
	int s, q, ind;
} a[maxn];

bool comp(S a, S b)
{
	return a.s*b.q < b.s*a.q;
}

int main(void)
{
	scanf("%d %lld", &n, &w);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &a[i].s, &a[i].q);
		a[i].ind = i;
	}

	sort(a+1, a+n+1, comp);

	int ans = 0;

	priority_queue<pii> fila;
	ll soma = 0;

	vector<int> V;

	for (int i = 1; i <= n; i++)
	{
		if (1ll*a[i].s > w) continue;

		fila.push({a[i].q, i});
		soma += 1ll*a[i].q;

		while (1ll*a[i].s*soma > 1ll*w*a[i].q)
		{
			soma -= 1ll*fila.top().ff;
			fila.pop();
		}

		if (fila.size() > ans)
		{
			ans = fila.size();
			V.clear();

			while (!fila.empty())
			{
				V.push_back(fila.top().ss);
				fila.pop();
			}

			for (auto x: V)
				fila.push({a[x].q, x});
		}
	}

	printf("%d\n", ans);

	for (auto x: V)
		printf("%d\n", a[x].ind);
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |   if (fila.size() > ans)
      |       ~~~~~~~~~~~~^~~~~
hiring.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%d %lld", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
hiring.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d %d", &a[i].s, &a[i].q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 30
• Subtask 2: 10 / 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