Submission #1301539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301539		b_malinowski	Balloons (CEOI11_bal)	C++20	100 / 100	92 ms	7924 KiB

bal

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    i64 N;
    cin >> N;
    vector<i64> poz(N + 1);
    vector<i64> maks(N + 1);
    for (i64 i = 1; i <= N; i++)
    {
        cin >> poz[i] >> maks[i];
    }
    vector<double> roz(N + 1);
    poz[0] = -1e10; maks[0] = 1e9 + 7; roz[0] = 1e9 + 7;
    stack<i64> S;
    S.push(0);
    for (i64 i = 1; i <= N; i++)
    {
        double x1, r1, x2 = poz[i], r2 = maks[i];
        while (true)
        {
            x1 = poz[S.top()];
            r1 = roz[S.top()];
            r2 = min(r2, (x2 - x1) * (x2 - x1) / 4 / r1);
            if (r2 >= r1)
            {
                S.pop();
            }
            else
            {
                break;
            }
        }
        roz[i] = r2;
        S.push(i);
    }
    for (int i = 1; i <= N; i++)
    {
        cout << fixed << setprecision(10) << roz[i] << "\n";
    }

    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