Submission #1234051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234051		altern23	Let's Win the Election (JOI22_ho_t3)	C++20	21 / 100	640 ms	8376 KiB

Main

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

#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define fi first
#define sec second

const int MAXN = 5e2;
const ll INF = 2e18;

ll a[MAXN + 5], b[MAXN + 5];
ld dp[2][MAXN + 5][MAXN + 5];
ll sum[MAXN + 5];

int main(){ 
	ll N, K; cin >> N >> K;
	vector<pii> v(1);
	for(int i = 1; i <= N; i++){
		cin >> a[i] >> b[i];
        if(b[i] == -1) b[i] = INF;
		v.push_back({b[i], a[i]});
	}
	
	sort(v.begin(), v.end());
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j <= K; j++){
			for(int l = 0; l <= K; l++) dp[i][j][l] = INF;
		}
	}
	
	vector<ll> tmp;
	for(int i = N; i >= 1; --i){
		tmp.push_back(v[i].sec);
		sort(tmp.begin(), tmp.end());
		for(int k = 0; k < K - (i - 1) && k < (int)tmp.size(); k++) sum[i] += tmp[k];
	}
	
	ld ans = INF;
	for(int i = 0; i <= N; i++) dp[0][0][i] = 0;
	for(int i = 1; i <= K; i++){
		for(int k = 0; k <= i; k++){
			for(int l = 0; l <= K; l++){
				dp[i % 2][k][l] = INF;
				// take buff
				if(k && v[i].fi != INF) dp[i % 2][k][l] = min(dp[i % 2][k][l], dp[(i % 2) ^ 1][k - 1][l] + (1 / (1.0 * k)) * (1.0 * v[i].fi));
				// not take buff
				dp[i % 2][k][l] = min(dp[i % 2][k][l], dp[(i % 2) ^ 1][k][l] + (1 / (1.0 * (l + 1))) * (1.0 * v[i].sec));
			}
		}
		for(int j = 0; j <= i; j++){
			ans = min(ans, sum[i + 1] * (1 / (1.0 * (j + 1))) + dp[i % 2][j][j]);
		}
	}	

	cout << fixed << setprecision(10) << ans << "\n";
}

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