Submission #859145

#	Time	Username	Problem	Language	Result	Execution time	Memory
859145		Brek	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	99 ms	604 KiB

Main

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

pair<double, double> t[509];
double dp[509];
int n, k;

double wynik(int x) {
	for(int i = 0; i <= n; i++){
		dp[i] = 1000000000000000000;
	}
	dp[0] = 0;
	for(int i = 0; i < n; i++) {
		for(int j = min(i + 1, k - x); j >= 0; j--) {
			double popdp = dp[j];
			if(j > 0) {
				dp[j] = dp[j - 1] + t[i].second / (double)(x + 1);
			}
			else {
				dp[j] = 1000000000000000000;
			}
			if(0 < (i + 1) - j && (i + 1) - j <= x) {
				dp[j] = min(dp[j], popdp + t[i].first / (double)((i + 1) - j));
			}
			else {
				dp[j] = min(dp[j], popdp);
			}
		}
	}
	return dp[k - x];
}
int main(){
	cin>>n>>k;
	for(int i = 1; i <= n; i++){
		double a, b;
		cin>>a>>b;
		if(b == -1){
			b = 1000000000000000000;
		}
		t[i - 1] = {b, a};
	}
	sort(t, t + n);
	double w = 1000000000000000000;
	for(int i = 0; i <= k; i++){
		w = min(w, wynik(i));
	}
	cout<<fixed<<setprecision(5)<<w<<endl;
}

• 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