Submission #766609

#	Time	Username	Problem	Language	Result	Execution time	Memory
766609		NK_	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	9 ms	340 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;

const double eps = 1e-9;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cout << fixed << setprecision(15);

	int N, K; cin >> N >> K;
	V<int> A(N), B(N); 
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i]; 
		if (B[i] == -1) B[i] = int(1e9);
	}

	double ans = double(1e9);

	for(int c = 0; c <= N; c++) {
		V<int> BI(N); iota(begin(BI), end(BI), 0);
		
		sort(begin(BI), end(BI), [&](int i, int j) {
			return B[i] < B[j];
		});


		V<int> AI; for(int i = c; i < N; i++) AI.push_back(BI[i]);

		sort(begin(AI), end(AI), [&](int i, int j) {
			return A[i] < A[j];
		});

		V<int> ord; 

		double res = 0;
		for(int i = 0; i < c; i++) {
			// cout << BI[i] << " " << B[BI[i]] << endl;
			res += double(B[BI[i]]) / double(i + 1);
		}
		for(int i = 0; i < K - c; i++) {
			// cout << AI[i] << " " << A[AI[i]] << endl;
			res += double(A[AI[i]]) / double(c + 1);
		}

		// cout << c << " " << res << endl;

		if (res+eps < ans) ans = res;
	}
	cout << ans << nl;


    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23