Submission #937978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937978	2024-03-04T17:23:52 Z	Litusiano	Let's Win the Election (JOI22_ho_t3)	C++17	16 / 100	796 ms	596 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 1e18;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

bool cmp(pair<int,int> a, pair<int,int> b){
	if(a.second == b.second) return a.first<b.first;
	return a.second < b.second;
}

void shuffle(vector<pair<int,int>>& v){
	int n = v.size();
	for(int i = 0; i<3*n; i++){
		int a = rng()%n; int b = rng()%n;
		swap(v[a],v[b]);
	}
 
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout<<setprecision(3)<<fixed;
	int n,k1; cin>>n>>k1;

	vector<pair<int,int>> v(n);
	for(int i = 0; i<n; i++){
		cin>>v[i].first>>v[i].second;
		if(v[i].second == -1) v[i].second = INF;
	}
	if(n > 20){
		sort(v.begin(),v.end(),cmp);
		long double ans = 0;
		int cnt = 0;
		for(int i = 0; i<k1; i++){
			auto x = v[i];
			ans+=(1.0*x.first/(cnt+1));
			if(x.second == x.first) cnt++;
		}
		cout<<setprecision(10)<<fixed<<ans<<endl;
		return 0;
	}
	sort(v.begin(),v.end(),cmp);
	int q = 13000;
	long double ans = INF;
	while(q--){
		shuffle(v);
		long double dp[n+1][k1+1][k1+1];
		for(int i = 0; i<=n; i++){
			for(int j = 0; j<=k1; j++){
				for(int k = 0; k<=k1; k++) dp[i][j][k] = 1.0*INF;
			}
		}
		dp[0][0][0] = 0; // first i, j votes, k representants
		for(int i = 1; i<=n; i++){
			for(int j = 0; j<=k1; j++){
				for(int k = 0; k<=k1; k++){
					dp[i][j][k] = dp[i-1][j][k];
					if(!j) continue;
					long double act = dp[i-1][j-1][k]; // just speech for vote
					act+= 1.0*v[i-1].first/(k+1);
					dp[i][j][k] = min(dp[i][j][k],act);
					if(!k || v[i-1].second == INF) continue;
					act = dp[i-1][j-1][k-1];
					act+= 1.0*v[i-1].second / k;
					dp[i][j][k] = min(dp[i][j][k],act);
				}
			}
		}
		for(int k = 0; k<=k1; k++){
			ans = min(ans, dp[n][k1][k]);
		}
	}
	cout<<ans<<endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	344 KB	Output is correct
2	Correct	19 ms	348 KB	Output is correct
3	Correct	27 ms	348 KB	Output is correct
4	Correct	41 ms	344 KB	Output is correct
5	Correct	56 ms	348 KB	Output is correct
6	Correct	76 ms	436 KB	Output is correct
7	Correct	95 ms	344 KB	Output is correct
8	Correct	64 ms	428 KB	Output is correct
9	Correct	56 ms	348 KB	Output is correct
10	Correct	58 ms	548 KB	Output is correct
11	Correct	55 ms	348 KB	Output is correct
12	Correct	56 ms	344 KB	Output is correct
13	Correct	56 ms	428 KB	Output is correct
14	Correct	45 ms	348 KB	Output is correct
15	Correct	95 ms	440 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	344 KB	Output is correct
2	Correct	19 ms	348 KB	Output is correct
3	Correct	27 ms	348 KB	Output is correct
4	Correct	41 ms	344 KB	Output is correct
5	Correct	56 ms	348 KB	Output is correct
6	Correct	76 ms	436 KB	Output is correct
7	Correct	95 ms	344 KB	Output is correct
8	Correct	64 ms	428 KB	Output is correct
9	Correct	56 ms	348 KB	Output is correct
10	Correct	58 ms	548 KB	Output is correct
11	Correct	55 ms	348 KB	Output is correct
12	Correct	56 ms	344 KB	Output is correct
13	Correct	56 ms	428 KB	Output is correct
14	Correct	45 ms	348 KB	Output is correct
15	Correct	95 ms	440 KB	Output is correct
16	Correct	77 ms	348 KB	Output is correct
17	Correct	411 ms	460 KB	Output is correct
18	Correct	396 ms	464 KB	Output is correct
19	Correct	796 ms	596 KB	Output is correct
20	Incorrect	753 ms	488 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	344 KB	Output is correct
2	Correct	19 ms	348 KB	Output is correct
3	Correct	27 ms	348 KB	Output is correct
4	Correct	41 ms	344 KB	Output is correct
5	Correct	56 ms	348 KB	Output is correct
6	Correct	76 ms	436 KB	Output is correct
7	Correct	95 ms	344 KB	Output is correct
8	Correct	64 ms	428 KB	Output is correct
9	Correct	56 ms	348 KB	Output is correct
10	Correct	58 ms	548 KB	Output is correct
11	Correct	55 ms	348 KB	Output is correct
12	Correct	56 ms	344 KB	Output is correct
13	Correct	56 ms	428 KB	Output is correct
14	Correct	45 ms	348 KB	Output is correct
15	Correct	95 ms	440 KB	Output is correct
16	Correct	77 ms	348 KB	Output is correct
17	Correct	411 ms	460 KB	Output is correct
18	Correct	396 ms	464 KB	Output is correct
19	Correct	796 ms	596 KB	Output is correct
20	Incorrect	753 ms	488 KB	Output isn't correct
21	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	2 ms	344 KB	Output is correct
2	Correct	7 ms	452 KB	Output is correct
3	Correct	8 ms	348 KB	Output is correct
4	Correct	16 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Submission #937978

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 5.0

Subtask #3 11.0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 5.0

Subtask #3
11.0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0