oj.uz

Submission #928252

# Submission time Handle Problem Language Result Execution time Memory
928252 2024-02-16T06:13:38 Z pcc Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 284 ms 1039036 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define ld double

const ll inf = 1e12;
const ll mxn = 510;
pll arr[mxn];
ll N,K;
ld dp[mxn][mxn][mxn];
multiset<ll> st;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++)cin>>arr[i].sc>>arr[i].fs,arr[i].fs = (arr[i].fs == -1?inf:arr[i].fs);
	sort(arr+1,arr+N+1);
	for(auto &i:dp)for(auto &j:i)for(auto &k:j)k = inf;
	for(int i = 0;i<=N;i++)dp[0][i][0] = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 0;j<N;j++){
			for(int k = 0;k<=j;k++){
				auto tmp = dp[i-1][j][k];
				dp[i][j][k] = min(dp[i][j][k],tmp+arr[i].sc);
				dp[i][j][k+1] = min(dp[i][j][k+1],tmp+(arr[i].fs)/ld(k+1));
			}
		}
	}
	ld ans = inf;
	for(int i = N;i>K;i--){
		st.insert(arr[i].sc);
	}
	for(int i = K;i>=0;i--){
		ll sum = 0,C = K-i;
		for(auto it = st.begin();C&&it != st.end();it++,C--){
			sum += *it;
		}
		for(int j = 0;j<=i;j++){
			ld tans = sum/ld(j+1)+dp[i][j][j];
			ans = min(ans,tans);
		}
		st.insert(arr[i].sc);
	}
	cout<<fixed<<setprecision(20)<<ans<<'\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 1038580 KB Output is correct
2 Correct 133 ms 1038692 KB Output is correct
3 Correct 135 ms 1038672 KB Output is correct
4 Correct 134 ms 1038848 KB Output is correct
5 Correct 273 ms 1038676 KB Output is correct
6 Correct 271 ms 1038808 KB Output is correct
7 Correct 284 ms 1038932 KB Output is correct
8 Correct 276 ms 1038808 KB Output is correct
9 Correct 279 ms 1038864 KB Output is correct
10 Correct 281 ms 1038808 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 1038580 KB Output is correct
2 Correct 133 ms 1038692 KB Output is correct
3 Correct 135 ms 1038672 KB Output is correct
4 Correct 134 ms 1038848 KB Output is correct
5 Correct 273 ms 1038676 KB Output is correct
6 Correct 271 ms 1038808 KB Output is correct
7 Correct 284 ms 1038932 KB Output is correct
8 Correct 276 ms 1038808 KB Output is correct
9 Correct 279 ms 1038864 KB Output is correct
10 Correct 281 ms 1038808 KB Output is correct
11 Correct 131 ms 1038556 KB Output is correct
12 Correct 279 ms 1038736 KB Output is correct
13 Correct 276 ms 1038808 KB Output is correct
14 Correct 278 ms 1038800 KB Output is correct
15 Correct 280 ms 1038808 KB Output is correct
16 Correct 281 ms 1038932 KB Output is correct
17 Correct 277 ms 1039036 KB Output is correct
18 Correct 281 ms 1038672 KB Output is correct
19 Correct 276 ms 1038928 KB Output is correct
20 Correct 277 ms 1038804 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 1038836 KB Output is correct
2 Correct 137 ms 1038676 KB Output is correct
3 Correct 136 ms 1038720 KB Output is correct
4 Correct 135 ms 1038928 KB Output is correct
5 Correct 141 ms 1038676 KB Output is correct
6 Correct 131 ms 1038676 KB Output is correct
7 Correct 132 ms 1038600 KB Output is correct
8 Correct 132 ms 1038892 KB Output is correct
9 Incorrect 134 ms 1038708 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 1038836 KB Output is correct
2 Correct 137 ms 1038676 KB Output is correct
3 Correct 136 ms 1038720 KB Output is correct
4 Correct 135 ms 1038928 KB Output is correct
5 Correct 141 ms 1038676 KB Output is correct
6 Correct 131 ms 1038676 KB Output is correct
7 Correct 132 ms 1038600 KB Output is correct
8 Correct 132 ms 1038892 KB Output is correct
9 Incorrect 134 ms 1038708 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 1038836 KB Output is correct
2 Correct 137 ms 1038676 KB Output is correct
3 Correct 136 ms 1038720 KB Output is correct
4 Correct 135 ms 1038928 KB Output is correct
5 Correct 141 ms 1038676 KB Output is correct
6 Correct 131 ms 1038676 KB Output is correct
7 Correct 132 ms 1038600 KB Output is correct
8 Correct 132 ms 1038892 KB Output is correct
9 Incorrect 134 ms 1038708 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 1038580 KB Output is correct
2 Correct 133 ms 1038692 KB Output is correct
3 Correct 135 ms 1038672 KB Output is correct
4 Correct 134 ms 1038848 KB Output is correct
5 Correct 273 ms 1038676 KB Output is correct
6 Correct 271 ms 1038808 KB Output is correct
7 Correct 284 ms 1038932 KB Output is correct
8 Correct 276 ms 1038808 KB Output is correct
9 Correct 279 ms 1038864 KB Output is correct
10 Correct 281 ms 1038808 KB Output is correct
11 Correct 131 ms 1038556 KB Output is correct
12 Correct 279 ms 1038736 KB Output is correct
13 Correct 276 ms 1038808 KB Output is correct
14 Correct 278 ms 1038800 KB Output is correct
15 Correct 280 ms 1038808 KB Output is correct
16 Correct 281 ms 1038932 KB Output is correct
17 Correct 277 ms 1039036 KB Output is correct
18 Correct 281 ms 1038672 KB Output is correct
19 Correct 276 ms 1038928 KB Output is correct
20 Correct 277 ms 1038804 KB Output is correct
21 Correct 132 ms 1038836 KB Output is correct
22 Correct 137 ms 1038676 KB Output is correct
23 Correct 136 ms 1038720 KB Output is correct
24 Correct 135 ms 1038928 KB Output is correct
25 Correct 141 ms 1038676 KB Output is correct
26 Correct 131 ms 1038676 KB Output is correct
27 Correct 132 ms 1038600 KB Output is correct
28 Correct 132 ms 1038892 KB Output is correct
29 Incorrect 134 ms 1038708 KB Output isn't correct
30 Halted 0 ms 0 KB -