Submission #386047

#	Time	Username	Problem	Language	Result	Execution time	Memory
386047		ArianKheirandish	Balloons (CEOI11_bal)	C++14	100 / 100	229 ms	10348 KiB

bal

//in the name of god//
// SOBHET BEKHEIR JOOOOOOON E DEL

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef long long ll;
#define all(x)	x.begin(),x.end()
#define _ ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define pll pair<ll,ll>

const int maxn = 2e6 + 10;
const int MAX = 110;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;
int n;
double x[maxn], mxr[maxn], r[maxn];
stack < pair <double, double > > s;

int main(){_
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> x[i] >> mxr[i];

    r[1] = mxr[1];
    s.push(MP(x[1], mxr[1]));

    for(int i = 2; i <= n ; i++){
        r[i] = mxr[i];

        while (!s.empty()) {
            auto top = s.top();
            double prevX = top.F;
            double prevR = top.S;

            r[i] = min(r[i], (x[i] - prevX)*(x[i] - prevX)/(4 * prevR));

            if (r[i] >= prevR)
                s.pop();

            else
                break;
        }

        s.push(MP(x[i], r[i]));
    }

    for(int i = 1 ; i <= n ; i ++)
        cout << fixed << setprecision(3) << r[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