Submission #544813

#	Time	Username	Problem	Language	Result	Execution time	Memory
544813		blue	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	171 ms	2300 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using dd = double;
using vi = vector<int>;

const int mx = 500;
const dd INF = 1'000'000'0.0;

dd a[1+mx], b[1+mx];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	cout << std::fixed;
	cout.precision(10);

	b[0] = 0;
	for(int i = 1; i <= N; i++) cin >> a[i] >> b[i];

	vi I(1+N);
	for(int i = 0; i <= N; i++) I[i] = i;
	sort(I.begin(), I.end(), [] (int u, int v)
	{
		dd bu = b[u], bv = b[v];
		if(bu == -1) bu = INF;
		if(bv == -1) bv = INF;
		return bu < bv;
	});

// cerr << '\n';

	dd A[1+N], B[1+N];
	for(int i = 1; i <= N; i++) A[i] = a[I[i]], B[i] = b[I[i]];


	double res = INF;

	int cc = 0;
	for(int i = 1; i <= N; i++) cc += (B[i] != -1);

	// cerr <<"cc = " << cc << "\n";



	// 	cerr << "\n\n\n";
	// for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << B[i] << '\n';








	for(int x = 0; x <= min(K,cc); x++)
	{
		// cerr <<"\n\n\n\n x = " << x << '\n';
		dd DP[1+N][1+K-x]; //last position, non-collaborators
		for(int i = 0; i <= N; i++)
			for(int j = 0; j <= K-x; j++)
				DP[i][j] = INF;

		DP[0][0] = 0.0;

		for(int i = 1; i <= N; i++)
		{
			for(int j = 0; j <= min(i, K-x); j++)
			{
				// cerr << "\n\n state = " << i << ' ' << j << "/ " << i << ' ' << K-x << "\n";
				if(i-j > x)
					DP[i][j] = DP[i-1][j];

				if(i - j <= x && B[i] != -1 && i-j > 0)
				{
					// cerr << "#\n";
					// cerr << i-1 << ' ' << j << ' ' << i-j-1+1 << '\n';
					// cerr << "A\n";
					DP[i][j] = min(DP[i][j], DP[i-1][j] + (B[i] / double(i-j-1 + 1)));
				}

				if(j >= 1)
				{
					DP[i][j] = min(DP[i][j], DP[i-1][j-1] + (A[i] / double(x+1)));
				}

				// cerr << x << ' ' << i << ' ' << j << " : " << DP[i][j] << '\n';
			}
		}

		res = min(res, DP[N][K - x]);

		// cerr << "\n\n\n " << N << ' ' << K-x << ' ' << 1+N << ' ' << 1+x << "\n\n\n";
		
		// cerr << "res = " << res << "\n";
	}

	cout << res << '\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