Submission #576897

#	Time	Username	Problem	Language	Result	Execution time	Memory
576897		cheissmart	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	513 ms	1136 KiB

Main

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

vi pre[505];

signed main()
{
	IO_OP;

	int n, k;
	cin >> n >> k;
	V<pi> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i].S >> a[i].F;
		if(a[i].F == -1) a[i].F = INF;
	}
	sort(ALL(a));

	for(int he = 0; he < n; he++) {
		vi aux;
		for(int i = he; i < n; i++)
			aux.PB(a[i].S);
		sort(ALL(aux));
		pre[he] = aux;
	}

	auto solve = [&] (int be) {
		// b: 1, 1/2, 1/3..., 1/be 
		// a: 1/(be + 1)
		V<double> dp(be + 1, INF);
		dp[0] = 0;

		auto go = [&] (int he) {
			double ans = dp[be];
			vi aux = pre[he];
			for(int i = 0; i < k - he; i++)
				ans += 1. * aux[i] / (be + 1);
			return ans;
		};

		double ans = INF;
		ans = min(ans, go(0));
		for(int i = 0; i < k; i++) {
			V<double> ndp(be + 1, INF);
			for(int j = 0; j <= be; j++) if(dp[j] != INF) {
				// a
				ndp[j] = min(ndp[j], dp[j] + 1. * a[i].S / (be + 1));

				// b
				if(j + 1 <= be)
					ndp[j + 1] = min(ndp[j + 1], dp[j] + 1. * a[i].F / (j + 1));
			}
			swap(dp, ndp);
			ans = min(ans, go(i + 1));
		}

		return ans;
	};

	double ans = INF;
	for(int be = 0; be <= k; be++)
		ans = min(ans, solve(be));
	cout << fixed << setprecision(10) << ans << '\n';
}

• 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