Submission #938014

#	Time	Username	Problem	Language	Result	Execution time	Memory
938014		vjudge1	Let's Win the Election (JOI22_ho_t3)	C++17	77 / 100	2572 ms	1104 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

int N, K; 

void solve(){
	vector<pair<ld, ld>> v(N);
	bool special = true;
	for(int i = 0; i < N; i++){
		cin >> v[i].second >> v[i].first;
		if(v[i].first == -1) v[i].first = 1e9;
		else if(v[i].first != v[i].second) special = false;
	}
	sort(v.begin(), v.end());
	ld ans = 7e18;
	for(ld collaborators = 0; collaborators < K; collaborators++){
		vector<ld> dp(collaborators + 1, 1e18);
		dp[0] = 0;
		for(int i = 0; i < N; i++){
			for(ld j = collaborators; j >= 0; j--){
				if(j != collaborators) dp[j+1] = min(dp[j+1], dp[j] + v[i].first / (j+1.0));
				dp[j] += v[i].second / (collaborators+1.0);
			}
		}
		ans = min(ans, dp[collaborators]);
	}
	cout << fixed << setprecision(8) << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	if(K == N){
		solve();
		return 0;
	}
	vector<pair<ld, ld>> v(N);
	bool special = true;
	for(int i = 0; i < N; i++){
		cin >> v[i].second >> v[i].first;
		if(v[i].first == -1) v[i].first = 1e9;
		else if(v[i].first != v[i].second) special = false;
	}
	sort(v.begin(), v.end());
	ld ans = 7e18;
	if(special){
		for(int collaborators = 0; collaborators < K; collaborators++){
			ld cost = 0;
			ld hv = 1;
			for(int i = 0; i < collaborators; i++){
				cost += v[i].first / hv;
				hv++;
			}
			vector<ld> a;
			for(int i = collaborators; i < N; i++){
				a.push_back(v[i].second);
			}
			sort(a.begin(), a.end());
			for(int i = 0; i < K - collaborators; i++){
				cost += a[i] / hv;
			}
			ans = min(ans, cost);
		}
	}else{
		for(ld collaborators = 0; collaborators < K; collaborators++){
			vector<vector<ld>> dp(K+1, vector<ld>(collaborators + 1, 1e18));
			dp[0][0] = 0;
			for(int i = 0; i < N; i++){
				for(int elem = K - 1; elem >= 0; elem--){					
					for(ld j = collaborators; j >= 0; j--){
						if(j != collaborators) dp[elem+1][j+1] = min(dp[elem+1][j+1], dp[elem][j] + v[i].first / (j+1.0));
						dp[elem+1][j] = min(dp[elem+1][j], dp[elem][j] + v[i].second / (collaborators+1.0));
					}
				}
			}
			ans = min(ans, dp[K][collaborators]);
		}
	}
	cout << fixed << setprecision(8) << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:11:7: warning: variable 'special' set but not used [-Wunused-but-set-variable]
   11 |  bool special = true;
      |       ^~~~~~~

• 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: 0 / 23