Submission #526419

#	Time	Username	Problem	Language	Result	Execution time	Memory
526419		benson1029	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	1229 ms	994624 KiB

Main

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

int n;
int k;

pair<int,int> tmp[505];
int a[505], b[505];
double dp[505][505][505]; // dp: assume chosen number, first x, number of non-chosen
vector<int> t;

bool cmp(pair<int,int> a, pair<int,int> b) {
	if(a.first == -1) a.first = 1e9;
	if(b.first == -1) b.first = 1e9;
	return a < b;
} 

int main() {
	cin >> n >> k;
	for(int i=1; i<=n; i++) {
		cin >> a[i] >> b[i];
		tmp[i] = {b[i], a[i]};
	}
	sort(tmp+1, tmp+n+1, cmp);
	for(int i=1; i<=n; i++) {
		a[i] = tmp[i].second;
		b[i] = tmp[i].first;
	}
	double ans = 1e18;
	for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) dp[i][j][k] = 1e18;
	for(int i=0; i<=n; i++) dp[i][0][0] = 0;
	for(int i=0; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			for(int k=0; k<=j; k++) {
				if(k<j && b[j]!=-1) {
					dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k] + (b[j] * 1.0) / (j-k));
				}
				if(k>0) {
					dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k-1] + (a[j] * 1.0) / (i+1));
				}
			}
		}
	}
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=i; j++) {
			double v = dp[i-j][i][j];
			t.clear();
			for(int l=i+1; l<=n; l++) {
				t.push_back(a[l]);
			}
			sort(t.begin(), t.end());
			if(k-i > t.size()) continue;
			for(int l=0; l<k-i; l++) {
				v += (t[l] * 1.0) / (i-j + 1);
			}
			ans = min(v, ans);
		}
	}
	cout << fixed << setprecision(6) << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(k-i > t.size()) continue;
      |       ~~~~^~~~~~~~~~

• 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