Submission #887283

#	Time	Username	Problem	Language	Result	Execution time	Memory
887283		theghostking	Balloons (CEOI11_bal)	C++17	30 / 100	236 ms	14052 KiB

bal

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

#define int long long

long double ck(long double posi, long double posj, long double ri){
    long double on = ((posj - posi) * (posj - posi));
    return (on) / (4.0L * ri);
}

signed main() {
    int n;
    cin >> n;
    pair<long double, long double> bal[n];
    for (int i = 0; i < n; i++) {
        cin >> bal[i].first >> bal[i].second;
    }
    stack<pair<int, long double>> s;
    vector<long double> ans(n);
    ans[0] = bal[0].second;
    s.push({0, bal[0].second});
    for (int i = 1; i < n; i++) {
        ans[i] = bal[i].second;
        if (!s.empty()) {
            pair<int, long double> a = s.top();
            while (!s.empty()) {
                long double v = ck(bal[a.first].first, bal[i].first, a.second);
                ans[i] = min(ans[i], v);
                if (v >= ans[a.first]) {
                    s.pop();
                    if (!s.empty()) {
                        a = s.top();
                    }
                }
                else {
                    break;
                }
            }
        }
        if (!s.empty()) {
            pair<int, long double> a = s.top();
            ans[i] = min(ck(bal[a.first].first, bal[i].first, a.second), ans[i]);
        }
        s.push({i, ans[i]});
    }
    for (auto x : ans) {
        cout << fixed << setprecision(3) << x << '\n';
    }
    return 0;
}

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