Submission #888009

#	Time	Username	Problem	Language	Result	Execution time	Memory
888009		Hakiers	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	370 ms	6664 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int MAXN = 5e2 + 7;
constexpr ld oo = 1e9;
tuple<ld, ld, int> T[MAXN];
pair<ld, ld> TORG[MAXN];
pair<int, int> prevs[MAXN][MAXN];
ld dp[MAXN][MAXN];
bool blocked[MAXN];
ld sumA;
int n, k;

bool cmp1(tuple<ld, ld, int> a, tuple<ld, ld, int> b){
	auto [xa, ya, ia] = a;
	auto [xb, yb, ib] = b;
	
	if(ya != yb)
		return ya < yb;
	return xa < xb;
}

bool cmp2(tuple<ld, ld, int> a, tuple<ld, ld, int> b){
	auto [xa, ya, ia] = a;
	auto [xb, yb, ib] = b;
	
	if(xa != xb)
		return xa < xb;
	return ya < yb;
}

ld compute(ld val, ld l){
	return (sumA + val)/l;
}

void compute(){

	for(int i = 1; i <= n; i++){
		dp[i][1] = std::get<1>(T[i]) - std::get<0>(T[i]);
		prevs[i][1] = {0, std::get<2>(T[i])};
	}
	
		
	for(int l = 2; l <= k; l++){
		for(int i = l; i <= n; i++){
			ld actbest = (oo*oo);
			for(int j = l-1; j < i; j++){
				if(actbest > compute(dp[j][l-1] + dp[i][1], l)){
					prevs[i][l] = {j, std::get<2>(T[i])};
					dp[i][l] = dp[j][l-1] + dp[i][1];
					actbest = compute(dp[i][l], l);
				}
			}
		}
	}
}

vector<int> odtworz(int i, int l){
	vector<int> out;
	
	int pocz = i;
	
	while(l){
		out.push_back(prevs[pocz][l].second);
		//cout << "k: " << l << " " << out.back() << "\n";
		pocz = prevs[pocz][l--].first;
	}
	
	reverse(out.begin(), out.end());
	return out;
}

ld solve(){
	ld res = oo;
	sort(T+1, T+1+n, cmp2);
	
	for(int l = 0; l <= k-1; l++){
		for(int i = l; i <= n; i++){
			vector<int> odt = odtworz(i, l);
			ld act = 0;
			
			for(int z = 1; z <= l; z++){
				act += (TORG[odt[z-1]].second/z);
				blocked[odt[z-1]] = 1;
			}
			
			int it = k - l;
			
			for(int w = 1; w <= n && it > 0; w++){
				auto [xa, ya, ia] = T[w];
				if(blocked[ia]) continue;
				
				act += (xa / (l+1));
				it--;
			}
			
			for(auto u : odt)
				blocked[u] = 0;
			
			//cout << "k: " << l << " " << act << "\n";
			res = min(res, act);
		}
	}

	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++){
		ld a, b;
		cin >> a >> b;
		sumA += a;
		if(b == -1) b = 1e9;
		TORG[i] = {a, b};
		T[i] = {a, b, i};
		
	}
	
	sort(T+1, T+1+n, cmp1);
	compute();
	
	cout << fixed << setprecision(9) << solve() << "\n";

}

• 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