Submission #1216349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216349		trimkus	Let's Win the Election (JOI22_ho_t3)	C++20	11 / 100	2596 ms	468 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ld = long double;


int main() {
	int n, k;
	cin >> n >> k;
	vector<array<ld, 2>> a(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			cin >> a[i][j];	
		}
	}
	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	ld res = LLONG_MAX;
	vector<int> picked(n);
	auto gen = [&](auto& gen, int i, ld tim, ld pick, int have, vector<int>& ord) -> void {
		//~ if (ord[0] == 2) return;
		if (i == n) {
			if (have >= k) {
				//~ for (auto& u : ord) {
					//~ cerr << u << " ";
				//~ }
				//~ cerr << " = ";
				//~ cerr << tim << endl;
				//~ if (tim <= 42.167) {
					//~ for (auto& u : ord) {
						//~ cout << u << " ";
					//~ }
					//~ cout << "\n";
					//~ for (auto& u : ord) { 
						//~ cout << picked[u] << " ";
					//~ }
					//~ cout << "\n";
				//~ }
				res = min(res, tim);
			}
			return;
		}
		int j = ord[i];
		gen(gen, i + 1, tim, pick, have, ord);
		gen(gen, i + 1, tim + a[j][0] / pick, pick, have + 1, ord);
		if (a[j][1] != -1) {
			picked[j] = 1;
			gen(gen, i + 1, tim + a[j][1] / pick, pick + 1, have + 1, ord);
			picked[j] = 0;
		}
	};
	do {
		gen(gen, 0, 0, 1, 0, ord);
	} while (next_permutation(begin(ord), end(ord)));
	cout << fixed << setprecision(3) << res << "\n";
}

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