Submission #1255546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255546		chr34	Balloons (CEOI11_bal)	C++20	100 / 100	106 ms	3548 KiB

bal

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const int INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

double calc_r(pair<double, double> prev, double x){
	return (prev.first - x) * (prev.first - x) / (4 * prev.second);
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.in", "r", stdin);
	//freopen("input.out", "w", stdout);    
	int n; cin >> n;
	vector<double> ans(n);
	
	stack<pair<double, double>> s;
	for(int i = 0; i < n; ++i){
		double x, r; cin >> x >> r;
		double max_r = r;
		
		while(!s.empty()){
			pair<double, double> prev = s.top();
			double last_r = calc_r(prev, x);
			
			max_r = min(max_r, last_r);
			
			if(max_r >= prev.second){
				s.pop();
				continue;
			}
			else break;
		}
		
		s.push({x, max_r});
		
		ans[i] = max_r;
	}   
	
	cout<<fixed<<setprecision(3);
	for(double &r : ans) cout<<r<<endl;
    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