Submission #393977

#	Time	Username	Problem	Language	Result	Execution time	Memory
393977		Berted	Hiring (IOI09_hiring)	C++14	100 / 100	237 ms	19716 KiB

hiring

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

#define ll long long
#define pii pair<ll, ll>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;

const int SZ = (1 << 15), MX = 20000;

int N, cnt[MX + 1]; ll K;
ppi A[500001];

inline bool comp(const ppi &L, const ppi &R) {return L.fst.fst * R.fst.snd < L.fst.snd * R.fst.fst;}

int32_t main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++) 
	{
		cin >> A[i].fst.fst >> A[i].fst.snd; 
		A[i].snd = i;
	}
	sort(A, A + N, comp);

	int j = 0, c = 0, best = -1, bestIdx = -1; pii bestFrac = {-1, 1}; ll S = 0;
	for (int i = 0; i < N; i++)
	{
		cnt[A[i].fst.snd]++;
		if (A[i].fst.snd <= j) {S += A[i].fst.snd; c++;}
		for (; j < MX && (S + (ll)(j + 1) * cnt[j + 1]) * A[i].fst.fst <= A[i].fst.snd * K; j++)
		{
			S += (ll)(j + 1) * cnt[j + 1];
			c += cnt[j + 1];
		}
		for (; j && S * A[i].fst.fst > A[i].fst.snd * K; j--) 
		{
			S -= (ll)j * cnt[j];
			c -= cnt[j];
		}
		//cerr << i << ": " << A[i].fst.fst << " " << A[i].fst.snd << " " << j << "\n";
		int tp = (A[i].fst.snd * K - A[i].fst.fst * S) / (A[i].fst.fst * (ll)(j + 1));
		if (j == MX) {tp = 0;}
		int t = c + tp;
		pii f = {(A[i].fst.snd * K - A[i].fst.fst * (S + tp * (j + 1))), A[i].fst.snd};
		if ((t > best) || (t == best && f.fst * bestFrac.snd > f.snd * bestFrac.fst)) {best = t; bestFrac = f; bestIdx = i;}
	}

	pii frac = A[bestIdx].fst;
	for (int i = 0; i <= bestIdx; i++) {A[i].fst.fst = A[i].fst.snd; A[i].fst.snd = A[i].snd;}
	sort(A, A + bestIdx + 1);
	
	S = 0;
	vector<int> ans;

	for (int i = 0; i <= bestIdx; i++)
	{
		S += A[i].fst.fst;
		if (K * frac.snd < frac.fst * S) {break;}
		else {ans.push_back(A[i].snd + 1);}
	}

	cout << best << "\n";
	for (const int &x : ans) cout << x << "\n";
	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