Aquarium

/* ================================ MAKEFILE ===================================
 * CXXFLAGS=-std=c++20 -x c++ -Wall -fsanitize=undefined,address -pipe -g
 * ============================== CLion Setup ==================================
 * Alt F12 Rebind: File >> Setting >> Keymap >> Tool Windows >> Terminal */
// Basic
#include <bits/stdc++.h>                            
using namespace std;
using ll = long long;
const ll oo = *(ll*)"????????";
using vl = vector<ll>;
#define all(c) begin(c),end(c)
#define FOR(i,a,b) for (ll i=(a); i<(b); i++)
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)
// Graphs                    // ============== random numbers =================
using vvl = vector<vl>;      // mt19937 rng($semirandom)
#define pb push_back         // ============== primes =========================
#define sz(c) ll((c).size()) // seq $from $to | factor | grep -v ' .* '
// pll                       // 2^30: +3, +7, +9, +385, -407
using pll = pair<ll,ll>;     // 2^60: +33, +91, +933, -753
using vpll = vector<pll>;  // =============== stress test script ==============
#define xx first           // for((i=1;;++i)); do
#define yy second          //   echo $i
// double                  //   ./gen > in
using dd = double;         //   diff -w <(./A < in) <(./brute < in) || break
const dd eps = 1e-9;       // done

#define TR(X) ({ if(1) cerr << __LINE__ << ": " #X " = " << (X) << endl; })

int main() { 
    cin.sync_with_stdio(0); cin.tie(0); 
    ll n; cin >> n;
    vl h(n);
    for(ll &x : h) cin >> x;
    ll q;
    double V;
    cin >> q >> V;
    q--;
    double lo = 0, hi = V;

    cout << setprecision(10) << fixed;
    if(V <= h[q]){
        cout << V << endl;
        return 0;
    }

    FOR(it, 0, 100){
        double mid = (lo + hi) / 2;
        ll right = q, left = q;
        while(right < n - 1 && mid > max(h[right], h[right + 1]))
            right++;
        while(left > 0 && mid > max(h[left], h[left - 1]))
            left--;

        bool to_high = false;
        if(left == 0 && mid > h[left])
            to_high = true;
        if(right == n-1 && mid > h[right])
            to_high = true;

        if(!to_high){
            double w = (right - left + 1) * mid;
            if(w > V) to_high = true;
        }

        if(to_high)
            hi = mid;
        else lo = mid;
    }
    cout << lo << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED