Submission #859147

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

Main

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

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

bool cmp(pair<double, double> a, pair<double, double> b){
	return a.second < b.second;
}

double wynik(int x){
	for(int i = 0; i <= n; i++){
		dp[i] = 1000000000000000000;
	}
	//vector<double>dp(k - x + 1, 1e9);
	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].first / (double)(x + 1);
			}
			else {
				dp[j] = 1e9;
			}
			if(0 < (i + 1) - j && (i + 1) - j <= x) {
				dp[j] = min(dp[j], popdp + t[i].second / (double)((i + 1) - j));
			}
			else {
				dp[j] = min(dp[j], popdp);
			}
		}
	}
	return dp[k - x];
}

int main(){
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		cin>>t[i].first>>t[i].second;
		if(t[i].second == -1) t[i].second = 1000000000000000120;
	}
	sort(t, t + n, cmp);
	for(int i = 0; i <= k; i++){
		w = min(w, wynik(i));
	}
	cout<<fixed<<setprecision(9)<<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