Submission #670961

#	Time	Username	Problem	Language	Result	Execution time	Memory
670961		a_aguilo	Balloons (CEOI11_bal)	C++14	0 / 100	2056 ms	16056 KiB

bal

#include<bits/stdc++.h>
 
using namespace std;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
 
int n;
 
long double radius(int d, long double r){
    return (long double)(d*d)/(4*r);
}
 
int main(){
    cin >> n;
    vector<pair<int, long double>> MyStack;
    //Mystack[i] = {position, radius}
    vector<long double> answers(n);
    vi position(n);
    vi limit(n);
    for(int i = 0; i < n; ++i) cin >> position[i] >> limit[i];
 
    answers[0] = limit[0];
    MyStack.push_back({position[0], (long double)limit[0]});
    for(int i = 1; i < n; ++i){
        int it = MyStack.size()-2;
        while(it >= 0 and (radius(position[i]-MyStack[it].first, MyStack[it].second) < radius(position[i]-MyStack[it+1].first, MyStack[it+1].second)) and ((long double)limit[i] > radius(position[i]-MyStack[it+1].first, MyStack[it+1].second) ) ){
            MyStack.pop_back();
            it--;
        }
        long double rad = min((long double)limit[i], radius(position[i]-MyStack[MyStack.size()-1].first, MyStack[MyStack.size()-1].second) );
        MyStack.push_back({position[i], rad});
        answers[i] = rad;
    }
    cout << fixed << setprecision(3);
    for (long double ans: answers) cout << ans << endl;
 
    return 0;
}

• Subtask 1: 0 / 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