Submission #1246529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246529		ebrambill	Let's Win the Election (JOI22_ho_t3)	C++17	5 / 100	43 ms	424 KiB

Main

//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;
}

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