oj.uz

Submission #748922

# Submission time Handle Problem Language Result Execution time Memory
748922 2023-05-27T07:00:58 Z aaargh Hiring (IOI09_hiring) C++17
28 / 100
 1500 ms 35984 KB 
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

signed main() {
	io; int n, w;
	cin >> n >> w;
	double s[n], q[n];
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> q[i];
	}

	double cost;
	double ans;
	vector<double> fiine;
	vector<double> fiine2;
	double global_max = 0;
	double temp = 0;
	multiset<pair<double,int>> v;
	for (int i = 0; i < n; i++) {
		cost = s[i];
		ans = 1;
		v.clear();
		fiine.clear();
		fiine.push_back(i+1);
		// set i as being paid s[i] and take it by default
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			temp = (q[j]/q[i])*s[i];
			if (temp >= s[j]) v.insert({temp,j+1});
		}


		for (auto e: v) {
			if (cost+e.first <= w) {
				ans++;
				cost += e.first;
				fiine.push_back(e.second);
				// cerr << "pushing back " << e.second << nl;
			} else break;
		}
		global_max = max(global_max, ans);
		if (global_max == ans) {
			fiine2 = fiine;
			// cerr << "hi i am here "<< nl;
		}

	}
	cout << global_max << nl;
	for (int i = 0; i < global_max; i++) cout << fiine2[i] << nl;


}




/*
fix a c (double) that each person is paid times their qual
cost must be more than or equal to c times sum of qualifications
maintain pq sorted people you can use in increasing q
increase value of c, add more to pq
once sum of everyone in pq exceeds how much you can use, pop max qual out
c is some value of sk/qk




*/

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 1 ms 212 KB Partially correct
4 Partially correct 1 ms 212 KB Partially correct
5 Partially correct 1 ms 340 KB Partially correct
6 Partially correct 182 ms 456 KB Partially correct
7 Partially correct 317 ms 504 KB Partially correct
8 Partially correct 721 ms 568 KB Partially correct
9 Execution timed out 1513 ms 736 KB Time limit exceeded
10 Execution timed out 1575 ms 792 KB Time limit exceeded
11 Execution timed out 1573 ms 852 KB Time limit exceeded
12 Execution timed out 1575 ms 1244 KB Time limit exceeded
13 Execution timed out 1580 ms 1116 KB Time limit exceeded
14 Execution timed out 1578 ms 1536 KB Time limit exceeded
15 Execution timed out 1562 ms 1740 KB Time limit exceeded

Subtask #2
10.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 1577 ms 2372 KB Time limit exceeded
5 Execution timed out 1557 ms 5868 KB Time limit exceeded
6 Execution timed out 1531 ms 26480 KB Time limit exceeded
7 Execution timed out 1504 ms 33204 KB Time limit exceeded

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 340 KB Partially correct
2 Partially correct 17 ms 320 KB Partially correct
3 Correct 16 ms 380 KB Output is correct

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 380 KB Partially correct
2 Partially correct 39 ms 340 KB Partially correct
3 Correct 40 ms 340 KB Output is correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 73 ms 328 KB Partially correct
2 Partially correct 78 ms 400 KB Partially correct
3 Correct 71 ms 324 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 9932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1518 ms 17332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 35984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 35324 KB Time limit exceeded
2 Halted 0 ms 0 KB -