Submission #530322

#	Time	Username	Problem	Language	Result	Execution time	Memory
530322		yungyao	Let's Win the Election (JOI22_ho_t3)	C++17	23 / 100	675 ms	312 KiB

Main

using namespace std;
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define iter(x) x.begin(),x.end()
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 0, mod = 0;
const LL inf = 0;

#include <iomanip>
void solve2(int n, int k){
	int a[20], b[20];

	REP0(i, n) cin >> a[i] >> b[i];
	double ans = 1e9;
	REP0(mask, 1 << n){
		int m = __builtin_popcount(mask);
		if (m > k) continue;
		bool ok = true;
		REP0(i, n) if (((mask >> i) & 1) and b[i] == -1){
			ok = false;
			break;
		}
		if (!ok) continue;

		vector <int> bs, as;
		REP0(i, n){
			if ((mask >> i) & 1) bs.pb(b[i]);
			else as.pb(a[i]);
		}
		sort(iter(as));
		sort(iter(bs));
		double tans = 0;
		REP0(i, m) tans += bs[i] * 1.0 / (i+1);
		REP0(i, k - m) tans += as[i] * 1.0 / (m+1);
		ans = min(ans, tans);
	}
	cout << ans;
}

void solve(){
	cout << fixed << setprecision(15);
	int n, k;

	cin >> n >> k;
	if (n <= 20){
		solve2(n, k);
		return;
	}
}

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

	solve();

	return 0;
}

• Subtask 1: 0 / 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