Submission #1207747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207747		catsarecool5530	Balloons (CEOI11_bal)	C++20	100 / 100	98 ms	5356 KiB

bal

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
#define int long long
int MOD = 1e9 + 7;
const ll INF = 1e18;

long double calc(long double x1, array<long double, 2> top) {
    return pow(x1 - top[0], 2) / 4 / top[1];
}

void solve() {
    int n; cin >> n;
    vector<array<long double, 2>> stack;
    // stack[i] = {x coord, height}
    vector<long double> ans(n);
    for (int i = 0; i < n; i++) {
        int x; long double max_r; cin >> x >> max_r;
        while (!stack.empty()) {
            array<long double, 2> top = stack.back();
            max_r = min(max_r, calc(x, top));
            if (top[1] <= max_r) {
                stack.pop_back();
            } else {
                break;
            }
        }
        ans[i] = max_r;
        stack.push_back({(long double)x, max_r});
    }
    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(3) << ans[i] << endl;
    }





}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    // freopen("walk.in", "r", stdin);
    // freopen("walk.out", "w", stdout);
    ll t = 1; //cin >> t;
    while (t--) {
        solve();
    }
}

• 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