Submission #866272

#	Time	Username	Problem	Language	Result	Execution time	Memory
866272		dio_2	Balloons (CEOI11_bal)	C++17	100 / 100	115 ms	11816 KiB

bal

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

using ld = long double;
using ll = long long;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin >> N;
	
	vector<ll> x(N), r(N);
	vector<ld> ans(N);
	
	for(int i = 0;i < N;i++){
		cin >> x[i] >> r[i];
	}
	
	auto Calc = [&](int i, int j)->ld{
		ld radius_j = ans[j];
		return (ld(x[i]*x[i]+x[j]*x[j]-2*x[i]*x[j])) / (4 * radius_j);
	};
	
	//~ ans[0] = r[0];
	//~ cout << fixed << setprecision(3) << ans[0] << '\n';
	
	//~ for(int i = 1;i < N;i++){ O(N^2) BRUTE FORCE
		//~ 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';
	//~ }
	
	stack<int> st;
	for(int i = 0;i < N;i++){
		ld res = r[i];
		while(!st.empty()){
			int id = st.top();
			res = min(res, Calc(i, id));
			if(res >= ans[id]) st.pop();
			else break;
		}
		ans[i] = res;
		st.push(i);
		cout << fixed << setprecision(3) << res << '\n';
	}
	
	return 0;
}

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