Submission #653871

#	Time	Username	Problem	Language	Result	Execution time	Memory
653871		zxcvbnm	Balloons (CEOI11_bal)	C++14	100 / 100	200 ms	8124 KiB

bal

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<long double> x(n), r(n);
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> r[i];
	}
	
	stack<int> st;
	for(int i = 0; i < n; i++) {
		long double curr = r[i];
		while(!st.empty()) {
			int idx = st.top();
			curr = min(curr, (long double) ((x[i] - x[idx]) * (x[i] - x[idx])) / (4.00 * r[idx]));
			if (r[idx] <= curr) {
				st.pop();
			}
			else {
				break;
			}
		} 
		r[i] = curr;
		st.push(i);
		cout << fixed << setprecision(3) << curr << "\n";
	}
}

• 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