Submission #1281136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281136		SmuggingSpun	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	406 ms	532 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++){
			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]);
				}
			}
			if(__builtin_popcount(mask) == k){
				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);
				if(k - i - 1 <= A.size()){
					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;
	}
}
namespace sub5{
	void solve(){
		vector<int>p(n);
		iota(p.begin(), p.end(), 1);
		sort(p.begin(), p.end(), [&] (int i, int j){
			return a[i] < a[j];
		});
		double ans = 0;
		for(int i = 0; i < k; i++){
			ans += a[p[i]];
		}
		sort(p.begin(), p.end(), [&] (int i, int j){
			return b[i] < b[j];
		});
		for(int i = 1; i < k; i++){
			vector<vector<double>>dp(i + 1, vector<double>(k - i + 1, 1e18));
			for(int j = dp[0][0] = 0; j < n; j++){
				for(int x = i; x > -1; x--){
					for(int y = k - i; y > -1; y--){
						if(b[p[j]] != -1 && x > 0){
							minimize(dp[x][y], dp[x - 1][y] + double(b[p[j]]) / double(x));
						}
						if(y > 0){
							minimize(dp[x][y], dp[x][y - 1] + double(a[p[j]]) / double(i + 1));
						}
					}
				}
			}
			minimize(ans, dp[i][k - i]);
		}
		cout << setprecision(9) << fixed << ans;
	}
}
namespace sub67{
	void solve(){
		vector<int>p(n);
		iota(p.begin(), p.end(), 1);
		for(int i = 1; i <= n; i++){
			if(b[i] == -1){
				b[i] = 2e9;
			}
		}
		sort(p.begin(), p.end(), [&] (int i, int j){
			return b[i] < b[j] || (b[i] == b[j] && a[i] < a[j]);
		});
		double ans = 1e18;
		for(int i = 0; i < k; i++){
			vector<double>dp(n + 1, 1e18);
			for(int x = dp[0] = 0; x <= n; x++){
				vector<double>ndp(n + 1, 1e18);
				for(int y = 0; y <= x; y++){
					int yy = min(i, x - y);
					if(yy + y == k && yy == i){
						minimize(ans, dp[y]);
					}
					if(x < n){
						minimize(ndp[y + 1], dp[y] + double(a[p[x]]) / double(i + 1));
						minimize(ndp[y], dp[y] + (yy == i ? 0 : double(b[p[x]]) / double(yy + 1)));
					}
				}
				swap(dp, ndp);
			}
		}
		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();
	}
	else if(n <= 100){
		sub5::solve();
	}
	else{
		sub67::solve();
	}
}

Compilation message (stderr)

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

• 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