Submission #1309373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309373		thuhienne	Let's Win the Election (JOI22_ho_t3)	C++20	28 / 100	2595 ms	456 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

int n,k;
int a[509],b[509];

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n >> k;
	for (int i = 1;i <= n;i++) cin >> a[i] >> b[i];

	double res = 1e9;

	for (int mask = 0;mask < (1 << n);mask++) {
		bool checkmask = 1;
		for (int i = 1;i <= n;i++) if ((mask >> (i - 1) & 1) && b[i] == -1) {
			checkmask = 0;
			break;
		}
		if (!checkmask) continue;
		
		vector <int> more;
		for (int i = 1;i <= n;i++) if (mask >> (i - 1) & 1) more.push_back(b[i]);
		
		sort(more.begin(),more.end());
		double totaltime = 0;int cnt = 1;
		
		for (int i = 0;i < more.size();i++) {
			totaltime += 1.0 * more[i] / cnt;
			cnt++;
		}
		
		more.clear();
		for (int i = 1;i <= n;i++) if (!(mask >> (i - 1) & 1)) more.push_back(a[i]);
		
		sort(more.begin(),more.end());
		int voted = cnt - 1;
		for (int i = 0;i < more.size() && voted < k;i++) {
			totaltime += 1.0 * more[i] / cnt;
			voted++;
		}
		
		res = min(res,totaltime);
		
	}
	
	cout << setprecision(4) << fixed << res;

}

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