Submission #526439

#	Time	Username	Problem	Language	Result	Execution time	Memory
526439		sidon	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	430 ms	2364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dd double
#define minim(X, Y) (X = min(X, Y))

const int Z = 502, INF = 1e18;

int N, K, A[Z], B[Z];
dd ans = INF;
array<int, 2> s[Z];

dd dp[2][Z];
int suf[Z][Z];

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;

	for(int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
		if(B[i] < 0) B[i] = INF;
		s[i] = {B[i], A[i]};
	}

	sort(s, s + N);

	for(int i = 0; i < N; ++i) {
		A[i] = s[i][1];
		B[i] = s[i][0];
	}

	for(int i = 0; i < N; ++i) {
		vector<int> v;
		for(int j = i; j < N; ++j) v.push_back(A[j]);
		sort(begin(v), end(v));

		for(int j = 0, sum = 0; j < (int)size(v); ++j)
			suf[i][j+1] = (sum += v[j]);
	}

	for(int c = 0; c <= N; ++c) {
		fill(dp[1], dp[1] + N + 1, INF);
		dp[1][0] = 0;

		for(int i = 0; i < N; ++i) {
			auto &curr = dp[i & 1];
			auto &prev = dp[!(i & 1)];

			for(int k = 0; k <= N; ++k)
				curr[k] = prev[k] + dd(A[i]) / dd(c + 1);

			for(int k = 0; k < N; ++k)
				minim(curr[k+1], prev[k] + dd(B[i]) / dd(k + 1));

			for(int k = 0; k <= N; ++k) {
				int other = (i + 1) - k;
				if(other > K - c) curr[k] = INF;
			}

			int other = K - (i + 1);

			if(0 <= other && other <= (N - i - 1))
				minim(ans, curr[c] + dd(suf[i+1][other]) / dd(c + 1));
		}
	}

	ans = min(ans, dd(suf[0][K]));

	cout << setprecision(10) << fixed << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23