Submission #1210556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210556		ByeWorld	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	1721 ms	6296 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define pb push_back
#define ld double
using namespace std;
const int MAXN = 2e5+10;
const ld INF = 1e9+10;
typedef pair<int,int> pii;
void chmn(auto &a, auto b){ a = min(a, b); }

int n, k;
int p[MAXN], q[MAXN], a[MAXN], b[MAXN];
ld ans = INF;
ld dp[3][510][510];

ld coba(int col){
	for(int i=0; i<=2; i++) 
		for(int take=0; take<=col; take++) // ambil b
			for(int oth=0; oth<=k-col; oth++) // ambil a
				dp[i][take][oth] = INF;

	dp[0][0][0] = 0;
	for(int i=1; i<=n; i++){
		for(int take=0; take<=col; take++){
			for(int oth=0; oth<=k-col; oth++){
				// gk ambil samsek
				dp[i%2][take][oth] = dp[(i-1)%2][take][oth];
				// ambil a
				if(oth>=1)
					dp[i%2][take][oth] = min(dp[i%2][take][oth],
						dp[(i-1)%2][take][oth-1] + (ld)a[i]/(col+1)); 
				// ambil b
				if(take>=1)
					dp[i%2][take][oth] = min(dp[i%2][take][oth],
						dp[(i-1)%2][take-1][oth] + (ld)b[i]/take );
			}
		}
	}
	// cout << col << ' ' << dp[n][col] << " pp\n";
	return dp[n%2][col][k-col];
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	vector<pii> vec;
	vec.pb({-1,-1});
	for(int i=1; i<=n; i++){
		cin>>p[i]>>q[i];
		if(q[i] == -1) q[i] = MAXN;
		vec.pb({q[i], i});
	}
	sort(vec.begin(), vec.end());
	for(int i=1; i<=n; i++)
		a[i] = p[vec[i].se], b[i] = q[vec[i].se];

	int l = 0, r = k, mid1, mid2;
	while(r-l>=3){
		mid1 = (l+l+r)/3; mid2 = (l+r+r+2)/3;
		ld le = coba(mid1), ri = coba(mid2);
		ans = min(ans, min(le, ri));

		if(le < ri) r = mid2;
		else l = mid1;
	}
	for(int i=l; i<=r; i++) ans = min(ans, coba(i));

	cout << fixed << setprecision(7) << ans << '\n';
}

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