Submission #1246529

#TimeUsernameProblemLanguageResultExecution timeMemory
1246529ebrambillLet's Win the Election (JOI22_ho_t3)C++17
5 / 100
43 ms424 KiB
//In the name of GOD

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

typedef tuple<long double, bool, int> tpi3;

const int maxN=5e2+5, maxA=1e3+5, inf=1e6;
int n, k, a[maxN], b[maxN], mark[maxN];

bool can(long double t){
	fill(mark+1, mark+n+1, 0);
	long double m=t;
	int v=1, cnt=0;
	while(cnt<n){
		tpi3 maxi={-inf, false, 0};
		for (int i=1; i<=n; i++){
			if(mark[i]<1) maxi=max(maxi, {m-a[i], false, i});
			if(mark[i]<2 and b[i]>0) maxi=max(maxi, {(t-((long double)(b[i])/v))*(v+1), true, i});
		}
		if(get<0>(maxi)<0) break;
		cnt+=(mark[get<2>(maxi)]<1);
		mark[get<2>(maxi)]++;
		t-=(long double)(get<1>(maxi) ? b[get<2>(maxi)] : a[get<2>(maxi)])/v;
		v+=get<1>(maxi);
		m=t*v;
	}
	return (cnt>=k);
}

int main(){
	cin >>n >>k;
	for (int i=1; i<=n; i++)
		cin >>a[i] >>b[i];

	long double l=0, r=maxN*maxA;
	while(r-l>0.00001){
		long double mid=(r+l)/2;
		if(can(mid)) r=mid;
		else l=mid;
	}
	cout <<fixed <<setprecision(10) <<r <<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...