Submission #843853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
843853	2023-09-04T16:02:23 Z	_Avocado_	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	1 ms	800 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	800 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	800 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct

Subtask #3

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	548 KB	Output is correct
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	548 KB	Output is correct
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	548 KB	Output is correct
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	800 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	548 KB	Output is correct
29	Incorrect	0 ms	344 KB	Output isn't correct
30	Halted	0 ms	0 KB	-