oj.uz

Submission #928261

# Submission time Handle Problem Language Result Execution time Memory
928261 2024-02-16T06:24:32 Z pcc Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 369 ms 1039160 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 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/ld(j));
				dp[i][j][k+1] = min(dp[i][j][k+1],tmp+(arr[i].fs)/ld(k+1));
			}
		}
	}

	/*
	for(int i = 0;i<=N;i++){
		for(int j = 0;j<=i;j++)cout<<i<<' '<<j<<":"<<dp[i][j][j]<<endl;
	}cout<<endl;

   */

	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 369 ms 1038740 KB Output is correct
2 Correct 132 ms 1038676 KB Output is correct
3 Correct 132 ms 1038672 KB Output is correct
4 Correct 135 ms 1038628 KB Output is correct
5 Correct 289 ms 1038804 KB Output is correct
6 Correct 274 ms 1038700 KB Output is correct
7 Correct 299 ms 1038808 KB Output is correct
8 Correct 274 ms 1038676 KB Output is correct
9 Correct 271 ms 1038800 KB Output is correct
10 Correct 277 ms 1038800 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 1038740 KB Output is correct
2 Correct 132 ms 1038676 KB Output is correct
3 Correct 132 ms 1038672 KB Output is correct
4 Correct 135 ms 1038628 KB Output is correct
5 Correct 289 ms 1038804 KB Output is correct
6 Correct 274 ms 1038700 KB Output is correct
7 Correct 299 ms 1038808 KB Output is correct
8 Correct 274 ms 1038676 KB Output is correct
9 Correct 271 ms 1038800 KB Output is correct
10 Correct 277 ms 1038800 KB Output is correct
11 Correct 132 ms 1038672 KB Output is correct
12 Correct 278 ms 1038800 KB Output is correct
13 Correct 276 ms 1038800 KB Output is correct
14 Correct 281 ms 1038676 KB Output is correct
15 Correct 288 ms 1038932 KB Output is correct
16 Correct 284 ms 1038796 KB Output is correct
17 Correct 281 ms 1038928 KB Output is correct
18 Correct 277 ms 1038804 KB Output is correct
19 Correct 279 ms 1038676 KB Output is correct
20 Correct 283 ms 1039160 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1038676 KB Output is correct
2 Correct 130 ms 1038672 KB Output is correct
3 Correct 130 ms 1038644 KB Output is correct
4 Correct 132 ms 1038796 KB Output is correct
5 Correct 130 ms 1038676 KB Output is correct
6 Correct 131 ms 1038680 KB Output is correct
7 Correct 136 ms 1038672 KB Output is correct
8 Correct 133 ms 1038676 KB Output is correct
9 Incorrect 134 ms 1038676 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1038676 KB Output is correct
2 Correct 130 ms 1038672 KB Output is correct
3 Correct 130 ms 1038644 KB Output is correct
4 Correct 132 ms 1038796 KB Output is correct
5 Correct 130 ms 1038676 KB Output is correct
6 Correct 131 ms 1038680 KB Output is correct
7 Correct 136 ms 1038672 KB Output is correct
8 Correct 133 ms 1038676 KB Output is correct
9 Incorrect 134 ms 1038676 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1038676 KB Output is correct
2 Correct 130 ms 1038672 KB Output is correct
3 Correct 130 ms 1038644 KB Output is correct
4 Correct 132 ms 1038796 KB Output is correct
5 Correct 130 ms 1038676 KB Output is correct
6 Correct 131 ms 1038680 KB Output is correct
7 Correct 136 ms 1038672 KB Output is correct
8 Correct 133 ms 1038676 KB Output is correct
9 Incorrect 134 ms 1038676 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 1038740 KB Output is correct
2 Correct 132 ms 1038676 KB Output is correct
3 Correct 132 ms 1038672 KB Output is correct
4 Correct 135 ms 1038628 KB Output is correct
5 Correct 289 ms 1038804 KB Output is correct
6 Correct 274 ms 1038700 KB Output is correct
7 Correct 299 ms 1038808 KB Output is correct
8 Correct 274 ms 1038676 KB Output is correct
9 Correct 271 ms 1038800 KB Output is correct
10 Correct 277 ms 1038800 KB Output is correct
11 Correct 132 ms 1038672 KB Output is correct
12 Correct 278 ms 1038800 KB Output is correct
13 Correct 276 ms 1038800 KB Output is correct
14 Correct 281 ms 1038676 KB Output is correct
15 Correct 288 ms 1038932 KB Output is correct
16 Correct 284 ms 1038796 KB Output is correct
17 Correct 281 ms 1038928 KB Output is correct
18 Correct 277 ms 1038804 KB Output is correct
19 Correct 279 ms 1038676 KB Output is correct
20 Correct 283 ms 1039160 KB Output is correct
21 Correct 131 ms 1038676 KB Output is correct
22 Correct 130 ms 1038672 KB Output is correct
23 Correct 130 ms 1038644 KB Output is correct
24 Correct 132 ms 1038796 KB Output is correct
25 Correct 130 ms 1038676 KB Output is correct
26 Correct 131 ms 1038680 KB Output is correct
27 Correct 136 ms 1038672 KB Output is correct
28 Correct 133 ms 1038676 KB Output is correct
29 Incorrect 134 ms 1038676 KB Output isn't correct
30 Halted 0 ms 0 KB -