oj.uz

Submission #393977

# Submission time Handle Problem Language Result Execution time Memory
393977 2021-04-25T05:55:24 Z Berted Hiring (IOI09_hiring) C++14
100 / 100
 237 ms 19716 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 3 ms 532 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 6 ms 844 KB Output is correct
15 Correct 6 ms 972 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 9 ms 1100 KB Output is correct
5 Correct 21 ms 2636 KB Output is correct
6 Correct 136 ms 9172 KB Output is correct
7 Correct 175 ms 12084 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4108 KB Output is correct
2 Correct 51 ms 4764 KB Output is correct
3 Correct 50 ms 4776 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6596 KB Output is correct
2 Correct 86 ms 7932 KB Output is correct
3 Correct 101 ms 7876 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 13376 KB Output is correct
2 Correct 206 ms 17604 KB Output is correct
3 Correct 209 ms 17600 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 15040 KB Output is correct
2 Correct 233 ms 19716 KB Output is correct
3 Correct 237 ms 19648 KB Output is correct