Submission #529581

#	Time	Username	Problem	Language	Result	Execution time	Memory
529581		fhvirus	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	2105 ms	4388 KiB

Main

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

#pragma GCC optimize("Ofast")

const ll MUL = 1e9;
const ll INF = 1e18;
const int kN = 505;
int N, K;
pii state[kN];
ll pool[2][kN][kN];

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

	cin >> N >> K;
	for (int i = 1; i <= N; ++i) {
		cin >> state[i].ff >> state[i].ss;
		if (state[i].ss == -1)
			state[i].ss = 1'000'000;
	}

	sort(state + 1, state + N + 1, [](const pii &a, const pii &b) {
		if (a.ss != b.ss) return a.ss < b.ss;
		return a.ff > b.ff;
	});

	auto dp = pool[0], sc = pool[1];
	ll ans = INF;
	for (int g = 0; g <= K; ++g) {
		for (int j = 0; j <= K; ++j)
			for (int k = 0; k <= g; ++k)
				dp[j][k] = sc[j][k] = INF;
		sc[0][0] = 0;
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j <= i and j <= K; ++j)
				if (i == j)
					for (int k = 0; k <= g; ++k) {
						dp[j][k] = sc[j][k];
						if (j > 0)
							dp[j][k] = min(dp[j][k], sc[j - 1][k] + state[i].ff * MUL / (g + 1));
						if (j > 0 and k > 0)
							dp[j][k] = min(dp[j][k], sc[j - 1][k - 1] + state[i].ss * MUL / k);
					}
				else {
					dp[j][g] = sc[j][g];
					if (j > 0)
						dp[j][g] = min(dp[j][g], sc[j - 1][g] + state[i].ff * MUL / (g + 1));
					if (j > 0 and g > 0)
						dp[j][g] = min(dp[j][g], sc[j - 1][g - 1] + state[i].ss * MUL / g);
				}
			swap(dp, sc);
		}
		ans = min(ans, sc[K][g]);
	}

	cout << setprecision(9) << fixed << ((double) ans / MUL) << '\n';
	return 0;
}

• 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