Submission #1186568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186568		matus192	Mobile (BOI12_mobile)	C++20	100 / 100	736 ms	39648 KiB

mobile

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define FOR(i, x) for (auto &i : x)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LONG_LONG_MAX
#define LMIN LONG_LONG_MIN
#define MOD 1000000007
#define SIR 1000000009

long double zisti(ll a, ll b, ll c, ll d) {
    long double x1 = a, y1 = b, x2 = c, y2 = d;
    long double r = (y2 * y2 - y1 * y1) / (x2 - x1);
    long double d1 = ((x2 - x1) + r) / 2;
    return x1 + d1;
}

long double distance(long double x1, long double y1, long double x2, long double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
    ll n, l;
    cin >> n >> l;
    vector<pii> inp(n);
    REP(i, 0, n) {
        cin >> inp[i].ff >> inp[i].ss;
    }

    vector<pll> s = {inp[0]};
    vector<long double> zmeny = {0};
    REP(i, 1, n) {
        auto [x2, y2] = inp[i];
        long double zmena = 1e9 + 1;
        while (!s.empty()) {
            auto [x1, y1] = s.back();
            zmena = zisti(x1, y1, x2, y2);
            if (zmena <= zmeny.back()) {
                s.pop_back();
                zmeny.pop_back();
            } else {
                break;
            }
        }
        if (zmena <= l) {
            zmena = max((long double)0, zmena);
            s.pb({x2, y2});
            zmeny.pb(zmena);
        }
    }
    zmeny.pb(l);

    int it = 0;
    long double mx = 0;
    for (auto [x, y] : s) {
        mx = max(mx, distance(x, y, zmeny[it], 0));
        mx = max(mx, distance(x, y, zmeny[it + 1], 0));
        it++;
    }
    cout << fixed << setprecision(3);
    cout << mx << '\n';

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5