Submission #1319604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319604		Jawad_Akbar_JJ	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	1823 ms	16248 KiB

Main

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;
const int N = 1005;
long double dp[N][N], a[N], b[N], inf = 1000000, Ans = inf, o = 1, cst;

signed main(){
	cout<<fixed<<setprecision(10);
	int n, k;
	cin>>n>>k;

	vector<pair<int, int>> vec = {{0, 0}};

	for (int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		if (b[i] == -1)
			b[i] = 1001;
		vec.push_back({b[i], a[i]});
	}
	sort(begin(vec) + 1, end(vec));

	for (int c=1;c<=n and vec[c - 1].first != 1001;c++){
		for (int i=0;i<N;i++){
			for (int j=0;j<N;j++)
				dp[i][j] = inf;
		}

		dp[0][0] = 0;

		for (int i=1;i<=n;i++){
			for (int v=0, clb;v<i;v++){
				clb = i - v, cst = 0;
				if (clb < c){
					if (vec[i].first != 1001)
						cst = (o * vec[i].first) / (o * clb);
					else
						cst = inf;
				}
				dp[i][v] = min(dp[i][v], dp[i-1][v] + cst);
			}
			for (int v=1;v<=i;v++)
				dp[i][v] = min(dp[i][v], dp[i-1][v - 1] + (o * vec[i].second) / (o * c));
		}
		Ans = min(Ans, dp[n][k - c + 1]);
	}
	cout<<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