Submission #923867

#	Time	Username	Problem	Language	Result	Execution time	Memory
923867		goodspeed0208	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	2614 ms	1018820 KiB

Main

#include<bits/stdc++.h>
#define pii pair<int, int>
#define INF 5000000
using namespace std;
 
bool cmp(pii a, pii b) {
	if (a.second == -1 && b.second == -1) return a.first < b.first;
	if (a.second == -1) return (1 > 2);
	if (b.second == -1) return (1 < 2);
	if (a.second == b.second) return a.first > b.first;
	return a.second < b.second;
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, K;
	cin >> n >> K;
	vector<pii>v(n+1);
	vector<double>a(n+1), b(n+1);
	for (int i = 1 ; i <=  n ;i++) cin >> v[i].first >> v[i].second;
	sort(v.begin()+1, v.end(), cmp);
	for (int i = 1 ; i <= n ;i++) a[i] = (double)v[i].first, b[i] = (double)v[i].second;
	
	vector<vector<vector<double> > >dp(505, vector<vector<double> >(505, vector<double>(505, INF)) );
	//double dp[505][505][505];
	dp[0][0][1] = 0.0;
	double ans = INF;
	for (int help = 1 ; help <= K ; help++) {
	    for (int i = 1 ; i <= n ; i++) {//first i people
	        //cout << i << ": \n";
    		for (int j = 0 ; j <= min(K, i) ; j++) {// have how many people
    			//cout << j << ": ";
    			for (int k = 1 ; k <= min(j+1, help) ; k++) {// get how many people
    				dp[i][j][k] = dp[i-1][j][k];
    				if (j > 0) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k] + (a[i] / help));
    				if (k > 1 && b[i] != -1) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k-1] + b[i] / (k-1));
    				//cout << dp[i][j][k] <<" ";
    				if (j == K && k == help) ans = min(ans, dp[i][j][k]);
    			}
    			//cout << "\n";
    		}
    	}
	}
	
	cout << fixed << setprecision(6) << ans << "\n";
	//for (auto &i : v) cout << i.first <<" " << i.second << "\n";
}

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