oj.uz

답안 #937975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937975 2024-03-04T17:22:13 Z Litusiano Let's Win the Election (JOI22_ho_t3) C++17
11 / 100
 872 ms 600 KB 
#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){
	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(auto x : v){
			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 = 14000;
	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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 8 ms 456 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 8 ms 456 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 43 ms 348 KB Output is correct
5 Correct 60 ms 348 KB Output is correct
6 Correct 79 ms 348 KB Output is correct
7 Correct 105 ms 344 KB Output is correct
8 Correct 60 ms 436 KB Output is correct
9 Correct 60 ms 600 KB Output is correct
10 Correct 60 ms 348 KB Output is correct
11 Correct 60 ms 348 KB Output is correct
12 Correct 60 ms 432 KB Output is correct
13 Correct 60 ms 436 KB Output is correct
14 Correct 44 ms 544 KB Output is correct
15 Correct 104 ms 348 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 43 ms 348 KB Output is correct
5 Correct 60 ms 348 KB Output is correct
6 Correct 79 ms 348 KB Output is correct
7 Correct 105 ms 344 KB Output is correct
8 Correct 60 ms 436 KB Output is correct
9 Correct 60 ms 600 KB Output is correct
10 Correct 60 ms 348 KB Output is correct
11 Correct 60 ms 348 KB Output is correct
12 Correct 60 ms 432 KB Output is correct
13 Correct 60 ms 436 KB Output is correct
14 Correct 44 ms 544 KB Output is correct
15 Correct 104 ms 348 KB Output is correct
16 Correct 82 ms 348 KB Output is correct
17 Correct 445 ms 468 KB Output is correct
18 Correct 431 ms 344 KB Output is correct
19 Correct 872 ms 492 KB Output is correct
20 Incorrect 824 ms 492 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 43 ms 348 KB Output is correct
5 Correct 60 ms 348 KB Output is correct
6 Correct 79 ms 348 KB Output is correct
7 Correct 105 ms 344 KB Output is correct
8 Correct 60 ms 436 KB Output is correct
9 Correct 60 ms 600 KB Output is correct
10 Correct 60 ms 348 KB Output is correct
11 Correct 60 ms 348 KB Output is correct
12 Correct 60 ms 432 KB Output is correct
13 Correct 60 ms 436 KB Output is correct
14 Correct 44 ms 544 KB Output is correct
15 Correct 104 ms 348 KB Output is correct
16 Correct 82 ms 348 KB Output is correct
17 Correct 445 ms 468 KB Output is correct
18 Correct 431 ms 344 KB Output is correct
19 Correct 872 ms 492 KB Output is correct
20 Incorrect 824 ms 492 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 8 ms 456 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -