Submission #530323

#	Time	Username	Problem	Language	Result	Execution time	Memory
530323		yungyao	Let's Win the Election (JOI22_ho_t3)	C++17	33 / 100	653 ms	324 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;
	}
	vector <int> a, b;
	REP(n){
		int aa, bb;

		cin >> aa >> bb;
		if (bb == -1) a.pb(aa);
		else b.pb(aa);
	}
	n = b.size(); int m = a.size();
	sort(iter(a));
	sort(iter(b));
	double ans = 1e9;
	REP0(i, min(n, k)+1){
		if (k - i > m) continue;

		double tans = 0;
		REP0(j, i) tans += b[j] * 1.0 / (j+1);
		REP0(j, k - i) tans += a[j] * 1.0 / (i+1);
		ans = min(ans, tans);
	}
	cout << ans;
}

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

	solve();

	return 0;
}

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