oj.uz

답안 #952049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952049 2024-03-23T04:34:00 Z Angus_Yeung Hiring (IOI09_hiring) C++17
100 / 100
 305 ms 17868 KB 
#include <bits/stdc++.h>
#define val first
#define id second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

struct worker {
	ll s, q, id;
};

ll n, w, sum;
pair<ll, long double> ans;
worker a[500010];
priority_queue<pii> q;

long double f(worker x) {
	return x.s*1.0/x.q;
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> w;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].s >> a[i].q;
		a[i].id = i;
	}
	sort(a+1, a+n+1, [&](worker x, worker y) -> bool {
		return f(x) < f(y);
	});
	
	sum = 0; ans = {0, 0};
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; i++) {
		q.push({a[i].q, a[i].id});
		sum += a[i].q;
		while (!q.empty() && f(a[i])*sum > w) {
			sum -= q.top().val;
			q.pop();
		}
		if ((ll)q.size() > ans.first) {
			ans = {(ll)q.size(), sum*f(a[i])};
		}
		else if ((ll)q.size() == ans.first && sum*f(a[i]) < ans.second) {
			ans = {(ll)q.size(), sum*f(a[i])};
		}
	}
	
	if (ans.first == 0) {
		cout << "0\n";
		return 0;
	}
	
	sum = 0;
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; i++) {
		q.push({a[i].q, a[i].id});
		sum += a[i].q;
		while (!q.empty() && f(a[i])*sum > w) {
			sum -= q.top().val;
			q.pop();
		}
		if (ans.first == (ll)q.size() && ans.second >= sum*f(a[i])) {
			cout << ans.first << "\n";
			while (!q.empty()) {
				cout << q.top().id << "\n";
				q.pop();
			}
			return 0;
		}
	}
	
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 6 ms 2908 KB Output is correct
15 Correct 7 ms 2908 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 2908 KB Output is correct
5 Correct 23 ms 3040 KB Output is correct
6 Correct 172 ms 11236 KB Output is correct
7 Correct 229 ms 15056 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 5860 KB Output is correct
2 Correct 62 ms 5892 KB Output is correct
3 Correct 65 ms 5840 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 8912 KB Output is correct
2 Correct 99 ms 8908 KB Output is correct
3 Correct 106 ms 8944 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 15816 KB Output is correct
2 Correct 267 ms 16492 KB Output is correct
3 Correct 258 ms 15736 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 17868 KB Output is correct
2 Correct 295 ms 17100 KB Output is correct
3 Correct 305 ms 17380 KB Output is correct