Submission #1327832

#TimeUsernameProblemLanguageResultExecution timeMemory
1327832tkm_algorithmsLet's Win the Election (JOI22_ho_t3)C++20
10 / 100
1 ms332 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;

bool cmp(P a, P b) {
	if (a.second != -1 && b.second != -1)return a.first < b.first;
	else if (a.second != -1)return 0;
	else if (b.second != -1)return 1;
	return a.first < b.first;
}

void solve() {
	int n, k; cin >> n >> k;
	vector<int> a, b;
	rep(i, 0, n) {
		int x, y; cin >> x >> y;
		if (y != -1)b.push_back(y);
		else a.push_back(x);
	}
	
	sort(all(a));
	sort(all(b));
	//for (auto &i: a)cin >> i.first >> i.second;
	
	//cout << sz(a) << nl;
	//sort(all(a), cmp);
	double res = -1;
	rep(i, 0, min(sz(b), k)+1) {
		if (k-i > sz(a))continue;
		int cnt = 1;
		double sm = 0;
		rep(j, 0, i) {
			sm += (double)(b[j])/double(cnt);
			cnt += 1;
		}
		rep(j, 0, k-i)
			sm += (double)(a[j])/double(cnt);
		if (res != -1)res = min(res, sm);
		else res = sm;
	}
	
	//double res = 0;
	//int cnt = 1;
	//rep(i, 0, n) {
		//res += (double)(a[i].first/cnt);
		//if (a[i].second != -1)cnt += 1;
	//}
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...