Submission #1137035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137035		sohamsen15	Global Warming (NOI13_gw)	C++20	6 / 40	748 ms	8264 KiB

gw

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n; cin >> n;
    vector<ll> a(n); for (auto &x: a) cin >> x;
    auto f = [&](double h) {
        ll ans = 0;
        bool curr = false;
        for (ll i = 0; i < n; i++)
            if (a[i] > h) {
                if (!curr) ans++;
                curr = true;
            } else curr = false;
        return ans;
    };

    ll mx = *max_element(a.begin(), a.end());
    ll best = 0;

    double l = 0, r = 2e31;
    while (r - l > 0.1) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;

        if (f(m1) < f(m2)) l = m1;
        else r = m2; 
    } 
    
    cout << max(f(l), max(f(l - 1), f(l + 1)));
}

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