Submission #1305622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305622		zadniprovska	Balloons (CEOI11_bal)	C++20	100 / 100	105 ms	8116 KiB

bal

#include <bits/stdc++.h>

using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
 
const ll DIM = 1e6 + 7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;
const ll bsize = 350;

ld x[DIM], r[DIM];

void solve() {

    ll n;
    cin >> n;

    stack<ll> st;
    for (int i=1; i<=n; i++) {
        cin >> x[i] >> r[i];

        while (!st.empty()) {

            ll j = st.top();

            r[i] = min(r[i], (ld)(x[i] - x[j])*(x[i] - x[j]) / (ld)(4 * r[j]));

            if (r[i] >= r[j]) st.pop();
            else break;

        }

        st.push(i);

    }

    for (int i=1; i<=n; i++) cout << fixed << setprecision(3) << r[i] << " ";
    

}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("248.in", "r", stdin);
    //freopen("248.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) {
        solve();
    }
    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