Submission #866258

#	Time	Username	Problem	Language	Result	Execution time	Memory
866258		dio_2	Balloons (CEOI11_bal)	C++17	40 / 100	2050 ms	7888 KiB

bal

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

using ld = long double;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin >> N;
	
	vector<int> x(N), r(N);
	vector<ld> ans(N);
	
	for(int i = 0;i < N;i++){
		cin >> x[i] >> r[i];
	}
	
	ans[0] = r[0];
	cout << fixed << setprecision(3) << ans[0] << '\n';
	
	#define X first
	#define Y second
	auto d = [&](pair<ld, ld> A, pair<ld, ld> B)->ld{
		return (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y);
	};
	
	/*
	3
	0 9
	8 1
	13 7
	*/
	auto Calc = [&](int i, int j)->ld{
		ld radius_j = ans[j];
		pair<ld, ld> centre_j = {x[j], radius_j};
	
		ld lo = 0, hi = r[i], mid;
		
		for(int rep = 0;rep < 70;++rep){
			mid = (lo + hi) / 2;
			ld radius_i = mid;
			pair<ld, ld> centre_i = {x[i], radius_i};
			if(d(centre_i, centre_j) >= (radius_i + radius_j) * (radius_i + radius_j))
				lo = mid;
			else 
				hi = mid;
		}
		
		return (lo + hi) / 2;
	};
	
	for(int i = 1;i < N;i++){
		ld use = r[i];
		for(int j = 0;j < i;j++){
			use = min(use, Calc(i, j));
		}
		ans[i] = use;
		cout << fixed << setprecision(3) << use << '\n';
	}
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10