oj.uz

Submission #863887

# Submission time Handle Problem Language Result Execution time Memory
863887 2023-10-21T10:35:30 Z phoenix0423 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 2500 ms 2872 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double, double> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const double INF = 1e18;

//enumerate number of b from 0 ... k - 1
//it is optimal to get collaboraters first then give speeches to k - #b people
//for a set of collaboraters, it is optimal to sort them by increasing bs

int main(void){
	fastio;
	int n, k;
	cin>>n>>k;
	vector<pll> a(n);
	for(int i = 0; i < n; i++){
		cin>>a[i].f>>a[i].s;
		if(a[i].s == -1) a[i].s = INF;
	}
	sort(a.begin(), a.end(), [&](pll a, pll b){ return a.s < b.s || (a.s == b.s && a.f < b.f);});
	double best = INF;
	for(int goal = 0; goal < k; goal++){ // enumerate number of collaboraters(can also tenary search)
		vector<vector<double>> dp(n + 1, vector<double>(k + 1, INF));
		dp[0][0] = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < goal; j++){
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i].f / (goal + 1));
				dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + a[i].s / (j + 1));
			}
		}
		for(int i = 0; i < n; i++){
			//choose k - i elements for second set
			vector<double> cand;
			for(int j = i; j < n; j++) cand.pb(a[j].f);
			sort(cand.begin(), cand.end());
			double cur = dp[i][goal];
			for(int j = 0; j < k - i; j++) cur += cand[j] / (goal + 1);
			best = min(best, cur);
		}
	}
	cout<<fixed<<setprecision(5)<<best<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 84 ms 664 KB Output is correct
6 Correct 219 ms 964 KB Output is correct
7 Correct 502 ms 1456 KB Output is correct
8 Correct 946 ms 2136 KB Output is correct
9 Correct 1427 ms 2740 KB Output is correct
10 Correct 735 ms 1964 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 84 ms 664 KB Output is correct
6 Correct 219 ms 964 KB Output is correct
7 Correct 502 ms 1456 KB Output is correct
8 Correct 946 ms 2136 KB Output is correct
9 Correct 1427 ms 2740 KB Output is correct
10 Correct 735 ms 1964 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 314 ms 1064 KB Output is correct
13 Correct 447 ms 1060 KB Output is correct
14 Correct 355 ms 1068 KB Output is correct
15 Correct 866 ms 1988 KB Output is correct
16 Correct 1222 ms 1896 KB Output is correct
17 Correct 1163 ms 1988 KB Output is correct
18 Correct 1337 ms 2508 KB Output is correct
19 Correct 1875 ms 2872 KB Output is correct
20 Correct 1611 ms 2848 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2563 ms 2472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 84 ms 664 KB Output is correct
6 Correct 219 ms 964 KB Output is correct
7 Correct 502 ms 1456 KB Output is correct
8 Correct 946 ms 2136 KB Output is correct
9 Correct 1427 ms 2740 KB Output is correct
10 Correct 735 ms 1964 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 314 ms 1064 KB Output is correct
13 Correct 447 ms 1060 KB Output is correct
14 Correct 355 ms 1068 KB Output is correct
15 Correct 866 ms 1988 KB Output is correct
16 Correct 1222 ms 1896 KB Output is correct
17 Correct 1163 ms 1988 KB Output is correct
18 Correct 1337 ms 2508 KB Output is correct
19 Correct 1875 ms 2872 KB Output is correct
20 Correct 1611 ms 2848 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 452 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Incorrect 1 ms 348 KB Output isn't correct
35 Halted 0 ms 0 KB -