Submission #473111

#	Time	Username	Problem	Language	Result	Execution time	Memory
473111		MohammadAghil	Balloons (CEOI11_bal)	C++14	100 / 100	274 ms	15392 KiB

bal

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const ll mod = 1e9 + 7, maxn = 2e3 + 10, inf = 1e18;

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector<long double> x(n), r(n), st, ans(n);
    rep(i,0,n){
        cin >> x[i] >> r[i];
    }
    cout << fixed << setprecision(5);
    rep(i,0,n){
        long double rx = r[i];
        while(sz(st)){
            rx = min(rx, (long double)(x[i] - x[st.back()])*(x[i] - x[st.back()])/(4.*ans[st.back()]));
            if(rx >= ans[st.back()]) st.pop_back();
            else break;
        }
        ans[i] = rx;
        st.pb(i);
        cout << ans[i] << ' ';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10