Submission #843853

#	Time	Username	Problem	Language	Result	Execution time	Memory
843853		_Avocado_	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	1 ms	800 KiB

Main

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

const int INF = 2e18;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	int n, k; cin>>n>>k;
	
	vector<array<int, 3>>bi(n);
	vector<array<int, 3>>ai(n);
	
	for(int i = 0; i<n; ++i){
		int a, b; cin>>a>>b;
		
		if(b == -1) b = INF;
		ai[i] = {a, b, i};
		bi[i] = {b, a, i};
	}
	
	sort(bi.begin(), bi.end());
	sort(ai.begin(), ai.end());
	
	vector<int>perm(n);
	
	for(int i = 0; i<n; ++i){
		perm[ai[i][2]] = i;
	}
	
	vector<long double>col_sum(n);
	col_sum[0] = bi[0][0];
	
	for(int i = 1; i<n; ++i){
		col_sum[i] = col_sum[i-1] + ((long double)bi[i][0]/(i+1));
	}
	
	//for(auto u: col_sum) cout<<u<<" ";
	//cout<<endl;
	
	int sum = 0;
	
	for(int i = 0; i<k; ++i) sum += ai[i][0];
	
	vector<int>taken(n);
	long double ans = sum;
	int index = k-1;
	
	for(int i = 0; i<k; ++i){
		while(index >= 0 && taken[index]) --index;
		
		if(perm[bi[i][2]] <= index){
			taken[perm[bi[i][2]]] = 1;
			sum -= bi[i][1];
		}
		else if(index != -1){
			sum -= ai[index][0];
			--index;
		}
			
		long double cur = col_sum[i] + ((long double)sum/(i+2));
		
		ans = min(ans, cur);
	}
	
	cout<<setprecision(10)<<ans;
	
	cout<<'\n';
}

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