답안 #863887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863887	2023-10-21T10:35:30 Z	phoenix0423	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	2500 ms	2872 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2563 ms	2472 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	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	-

답안 #863887

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 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
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0