Submission #869628

#	Time	Username	Problem	Language	Result	Execution time	Memory
869628		theghostking	Balloons (CEOI11_bal)	C++17	20 / 100	240 ms	11348 KiB

bal

    #include <bits/stdc++.h>
    using namespace std;
     
    long double ck(long double posi, long double posj, long double ri){
        long double on = ((posj - posi) * (posj - posi));
        return (on) / (4.0L * ri);
    }
     
    int 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), bal[i].second);
            }
            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: 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