Submission #869626

#	Time	Username	Problem	Language	Result	Execution time	Memory
869626		theghostking	Balloons (CEOI11_bal)	C++17	10 / 100	239 ms	10068 KiB

bal

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

double ck(double posi, double posj, double ri){
    int on = ((posj-posi)*(posj-posi));
    //cout << posi << " " << posj << " " << ri << "   " << on << " " << (1.0*on)/(4.0*ri) << "\n\n"; 
    return (1.0*on)/(4.0*ri);
}

int main() {
    int n;
    cin >> n;
    pair<double,double> bal[n];
    for (int i = 0; i<n; i++){
        cin >> bal[i].first >> bal[i].second;
    }
    stack<pair<int,double>> s;
    //index, how much it is inflated
    //monotonic stack
    vector<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,double> a = s.top();
            
            /*while ((!s.empty()) && (ck(a.first,bal[i].first,a.second) >= bal[i].second)){
                s.pop();
                if (!s.empty()){
                    a = s.top();
                }
            }*/
            while (!s.empty()){
                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,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: 0 / 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