제출 #1217525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217525		henrii	Balloons (CEOI11_bal)	C++20	100 / 100	305 ms	8340 KiB

bal

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define pii pair<int, int>
#define ll long long

struct Balloon
{
    long double x, r;
};

int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    int n;
    cin >> n;

    vector<Balloon> balloon(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> balloon[i].x >> balloon[i].r;
    }

    auto maxRadius = [&](int idx1, int idx2) -> long double
    {
        return (balloon[idx1].x - balloon[idx2].x) * (balloon[idx1].x - balloon[idx2].x) / (4.0 * balloon[idx1].r);
    };

    stack<pair<long double, int>> s;
    s.push({balloon[0].r, 0});
    for (int i = 1; i < n; ++i)
    {
        while (!s.empty())
        {
            balloon[i].r = min(balloon[i].r, maxRadius(s.top().second, i));
            if (balloon[i].r >= s.top().first) s.pop();
            else break;
        }

        s.push({balloon[i].r, i});
    }

    cout << fixed << setprecision(3);
    for (int i = 0; i < n; ++i)
    {
        cout << balloon[i].r << endl;
    }


    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