Submission #1309388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309388		thuhienne	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	219 ms	4420 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

int n,k;
pair <double,double> city[509];

double dp1[509][509],dp2[509][509];
//dp1 i j: min cost de thu phuc toan bo 1 -> i va co j colab
//dp2 i j: min cost de co j vote khi xet den i

int main() {
//  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n >> k;
	for (int i = 1;i <= n;i++) {
		cin >> city[i].first >> city[i].second;
		if (city[i].second == -1) city[i].second = 1e18;
	}
	
	sort(city + 1,city + 1 + n,[] (pair <double,double> a,pair <double,double> b) {
		return a.second < b.second;
	});
	
	double res = 1e18;
	
	for (int colab = 0;colab <= k;colab++) {
		
		for (int i = 0;i <= n;i++) for (int j = 0;j <= n;j++) dp1[i][j] = dp2[i][j] = 1e18;
		
		dp1[0][0] = dp2[0][0] = 0;
		
		for (int i = 1;i <= n;i++) {
			for (int j = 0;j <= min(i,colab);j++) {
				dp1[i][j] = dp1[i - 1][j] + city[i].first / (colab + 1);
				if (j) dp1[i][j] = min(dp1[i][j],dp1[i - 1][j - 1] + city[i].second / j);
			}
		}
		
		for (int i = colab;i <= n;i++) {
			dp2[i][i] = dp1[i][colab];
			for (int j = colab;j < i;j++) {
				dp2[i][j] = dp2[i - 1][j];
				
				if (j) dp2[i][j] = min(dp2[i][j],dp2[i - 1][j - 1] + city[i].first / (colab + 1));
			}
		}
		
		res = min(res,dp2[n][k]);
		
	}
	
	cout << setprecision(4) << fixed << res;

}

• 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