Submission #788307

#	Time	Username	Problem	Language	Result	Execution time	Memory
788307		math_pi	Balloons (CEOI11_bal)	C++14	10 / 100	150 ms	6000 KiB

bal

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

double calc(pair<double, double> p, double x) {
    return (p.first - x) * (p.first - x) / (4 * p.second);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    cin >> n;

    vector<double> res(n);
    stack<pair<double, double>> st;
    for(int i=0; i<n; i++) {
        double x, r;
        cin >> x >> r;
        double max_r = r;
        while(!st.empty()) {
            pair<double, double> last = st.top();
            double last_r = calc(last, x);

            max_r = min(max_r, last_r);

            if(max_r >= last.second) {
                st.pop();
            } else break;
        }
        
        res[i] = max_r;
        st.push({x, r});
    }

    cout << fixed << setprecision(3);

    for(auto &x: res) 
        cout << x << ' ';
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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