Submission #1281115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281115		SmuggingSpun	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	2 ms	424 KiB

Main

#include<bits/stdc++.h>
#define taskname "c"
using namespace std;
const int lim = 505;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
int n, k, a[lim], b[lim];
namespace sub12{
	void solve(){
		vector<int>p;
		for(int i = 1; i <= n; i++){
			if(b[i] != -1){
				p.push_back(i);
			}
		}
		sort(p.begin(), p.end(), [&] (int i, int j){
			return b[i] < b[j];
		});
		double ans = 0;
		vector<int>I(n);
		iota(I.begin(), I.end(), 1);
		sort(I.begin(), I.end(), [&] (int i, int j){
			return a[i] < a[j];
		});
		for(int i = 0; i < k; i++){
			ans += a[I[i]];
		}
		vector<bool>vis(n + 1, false);
		double sum = 0;
		for(int i = 0; i < min(int(p.size()), k); i++){
			vis[p[i]] = true;
			sum += double(b[p[i]]) / double(i + 1);
			double current = 0;
			int cnt = i + 1;
			for(int& j : I){
				if(cnt == k){
					break;
				}
				if(!vis[j]){
					current += double(a[j]) / double(i + 2);
					cnt++;
				}
			}
			if(cnt == k){
				minimize(ans, current + sum);
			}
		}
		cout << setprecision(9) << fixed << ans;
	}
}
namespace sub34{
	void solve(){
		for(int i = 0; i < n; i++){
			a[i] = a[i + 1];
			b[i] = b[i + 1];
		}
		double ans = 1e18;
		for(int mask = 0; mask < (1 << n); mask++){
			if(__builtin_popcount(mask) == k){
				bool f = true;
				double current = 0;
				vector<int>A, B;
				for(int i = 0; i < n; i++){
					if(mask >> i & 1){
						A.push_back(a[i]);		
						current += a[i];			
					}
					else if(b[i] != -1){
						B.push_back(b[i]);
					}
				}
				minimize(ans, current);
				sort(A.begin(), A.end());
				sort(B.begin(), B.end());
				double sum = 0;
				for(int i = 0; i < min(int(B.size()), k); i++){
					sum += double(B[i]) / double(i + 1);
					for(int j = current = 0; j < k - i - 1; j++){
						current += double(A[j]) / double(i + 2);
					}
					minimize(ans, sum + current);
				}
			}
		}
		cout << setprecision(9) << fixed << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	bool is_sub12 = true;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		if(b[i] != -1 && a[i] != b[i]){
			is_sub12 = false;
		}
	}
	if(is_sub12){
		sub12::solve();
	}
	else if(n <= 20){
		sub34::solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:94:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23