Submission #766626

#	Time	Username	Problem	Language	Result	Execution time	Memory
766626		NK_	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	14 ms	356 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-7;

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]; 
	}

	double ans = double(1e6);

	V<int> BI; 
	set<int> use; for(int i = 0; i < N; i++) use.insert(i);

	for(int c = 0; c <= N; c++) {
		V<int> AI; for(auto& x : use) AI.push_back(x);

		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;

		V<int> I; for(auto& x : use) if (B[x] != -1) I.push_back(x);
		
		sort(begin(I), end(I), [&](int i, int j) {
			int db = B[i] - B[j];
			int da = A[i] - A[j];
			
			// cout << i << " " << j << endl;
			// cout << A[i] << " " << B[i] << endl;
			// cout << A[j] << " " << B[j] << endl;
			// cout << db << " " << da << endl;
			// cout << int((db * (c + 2)) > (da * (c + 1))) << endl;
			// cout << endl;
			int L = (db * (c + 2));
			int R = (da * (c + 1));
			if (L == R) return (A[i] == A[j] ? B[i] > B[j] : A[i] > A[j]);
			return L < R;
		});

		if (size(I) == 0) break;

		int best = I.front();
		BI.push_back(best);
		use.erase(best);
		// cout << A[best] << " " << B[best] << endl;

		// cout << best << endl << endl;
	}
	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