Submission #1294648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294648		KindaGoodGames	Balloons (CEOI11_bal)	C++20	20 / 100	2096 ms	2912 KiB

bal

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,double>
#define pdd pair<double,double>
#define tiii tuple<int,int,int>

using namespace std;

double eps = 1e-4;

double dist(pdd a, pdd b){
    double dx = a.first-b.first;
    double dy = a.second-b.second;
    return sqrt((dx*dx)+(dy*dy));
}

double get(pii bal, int p){
    double l = 0;
    double r = 1e9;
    
    pdd point = {bal.first, bal.second};
    double ma = 0;
    while(r-l >= eps){
        double mid = (r+l)/2;
        pdd po = {p,mid};
        
        double d = dist(point, po);
        if(d >= mid+bal.second){
            ma = max(ma, mid);
            l = mid+eps;
        }else{
            r = mid-eps;
        }
    }
    return l;
}

int main(){
    int n;
    cin >> n;

    vector<int> arr(n);
    vector<double> constr(n);

    for(int i = 0; i < n; i++){
        cin >> arr[i] >> constr[i];
    }

    cout << fixed << setprecision(3);

    vector<pii> S;
    for(int i = 0; i < n; i++){
        double val = 1e9;
        for(auto v : S){
            val = min(val, get(v, arr[i]));
        } 
        val = min(val, constr[i]);
        while(S.size() && S.back().second <= val){
            S.pop_back();
        }
        S.push_back({arr[i],val});
        cout << val << "\n";
    }
    
}

• 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