제출 #1190291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190291		froxy09	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

int n, N;
vector<int> a;
vector<ll> segtree;

// Yardımçı: [l, r) aralığındakı minimumu sorğu (0‑indexed, N ağac ölçülü)
ll rangeMin(int l, int r) {
    ll res = INF;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, segtree[l++]);
        if (r & 1) res = min(res, segtree[--r]);
    }
    return res;
}

// DP rekursiyası: [l, r) aralığını baza h ilə sıfıra endirmək üçün minimal əməliyyat
ll solve(int l, int r, int h) {
    int len = r - l;
    if (len == 1) {
        // Yaponiya: əgər orijinal a-dan kənardayıqsa, xərclər 0
        if (l >= n) return 0;
        int need = a[l] - h;
        if (need == 0) return 0;
        if (need == 1) return 1;
        return INF;
    }
    int m = l + (len >> 1);

    // 1) Bütün aralıq üçün mövcud minimum
    ll mn = rangeMin(l, r);
    int cur = max(0LL, mn - h);

    // 2) Variant A: böyük seg‑ment götürmədən iki yarıya bölək
    ll res = solve(l, m, h) + solve(m, r, h);

    // 3) Variant B: bu səviyyədə bir dəfə 1 azaldan seg‑ment götürsək
    if (cur >= 1) {
        ll t = 1 + solve(l, m, h + 1) + solve(m, r, h + 1);
        res = min(res, t);
    }
    return res;
}

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

    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // N‑i tap: n‑dən ən yaxın yuxarı 2^k
    N = 1;
    while (N < n) N <<= 1;

    // Separator: segtree qurulması
    segtree.assign(2 * N, INF);
    for (int i = 0; i < n; i++) {
        segtree[N + i] = a[i];
    }
    for (int i = N - 1; i >= 1; i--) {
        segtree[i] = min(segtree[2 * i], segtree[2 * i + 1]);
    }

    ll ans = solve(0, N, 0);
    if (ans >= INF / 2) cout << -1 << "\n";
    else            cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70