Submission #529459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529459	2022-02-23T03:28:29 Z	fhvirus	Let's Win the Election (JOI22_ho_t3)	C++17	5 / 100	2 ms	204 KB

Main

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template<class I> void LKJ(I&&x) { cerr << x << endl; }
template<class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template<class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N; cin >> N;
	int K; cin >> K;
	int has_co = 0;
	vector<int> A(N), B(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
		has_co += (B[i] != -1);
	}

	vector<int> id(N);
	iota(AI(id), 0);
	sort(AI(id), [&](int u, int v) { return A[u] < A[v]; });

	int sum = 0;
	vector<int> in(N, 0);
	for (int i = 0; i < K; ++i) {
		sum += A[id[i]];
		in[id[i]] = 1;
	}

	double ans = sum;
	double cur = sum;
	int id_in_A = K - 1;
	vector<double> wei(N);
	for (int c = 1; c <= min(has_co, K - 1); ++c) {
		fill(AI(wei), 1e18);
		for (int i = 0; i < N; ++i) {
			if (in[i] == 2 or B[i] == -1) continue;
			if (in[i] == 1) {
				wei[i] = (B[i] - A[i]) / (double) c;
				wei[i] -= (sum - A[i]) * (1.0 / (c * (c + 1)));
			} else {
				wei[i] = (B[i] - A[id[id_in_A]]) / (double) c;
				wei[i] -= (sum - A[id[id_in_A]]) * (1.0 / (c * (c + 1)));
			}
		}
		int mni = min_element(AI(wei)) - begin(wei);
		assert(in[mni] != 2);
		if (in[mni] == 1) {
			sum -= A[mni];
		} else {
			sum -= A[id[id_in_A]];
			--id_in_A;
		}
		in[mni] = 2;
		cur += wei[mni];
		ans = min(ans, cur);
	}

	cout << setprecision(10) << fixed << ans << '\n';

	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct

Subtask #2

0 / 5.0

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

Subtask #3

0 / 11.0

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

Subtask #4

0 / 12.0

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

Subtask #5

0 / 33.0

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

Subtask #6

0 / 11.0

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

Subtask #7

0 / 23.0

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