Submission #656681

#	Time	Username	Problem	Language	Result	Execution time	Memory
656681		Nafeeszx	Balloons (CEOI11_bal)	C++14	30 / 100	197 ms	7496 KiB

bal

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define f first
#define s second
typedef long long ll;

const int mod = 1e9 + 7, MOD = 998244353;

int main()
{	
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<pair<double, double>> v(n);
    deque<pair<double, double>> rad;
    vector<double> res(n, 1e18);
    F0R(i, n) {
        cin >> v[i].first >> v[i].second;
    }
    F0R(i, n) {
        
        if(i == 0) {
            rad.push_back({v[i].first, v[i].second});
            res[i] = v[i].second;
            continue;
        }

        /*if(i == 8) {
            F0R(i, rad.size()) cout << rad[i].first << " ";
        }*/

        while(rad.size() > 1) {
            auto s = rad[rad.size()-1];
            auto t = rad[rad.size()-2];

            double a, b, ra, rb;
            tie(a, ra) = s;
            tie(b, rb) = t;

            double k = sqrt(ra/rb);
            double pp = (a - k * b) / (1 - k);

            if(pp >= v[i].first) break;
            rad.pop_back();
            //while(rad.size() > 1 && pp < v[i].first) rad.pop_back();

        }

        /*if(i == 8) {
            F0R(i, rad.size()) cout << rad[i].first << " ";
        }*/

        double opp = ((v[i].first - rad.back().first) * (v[i].first - rad.back().first)) / (4 * rad.back().second);
        res[i] = min(v[i].second, opp);
        while(!rad.empty() && rad[rad.size()-1].second <= res[i]) rad.pop_back();
        rad.push_back({v[i].first, res[i]});

    }

    F0R(i, n) {
        cout << fixed << setprecision(3) << res[i] << "\n";
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10