Submission #945228

#	Time	Username	Problem	Language	Result	Execution time	Memory
945228		fzyzzz_z	Bigger segments (IZhO19_segments)	C++17	100 / 100	85 ms	17068 KiB

segments

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const ll inf = 1e18 + 50;

ll solve(int n, vector<ll> & a) {
    // at i, for j > i s.t. s(i + 1, j) >= v_i upd(at_j, (ans_i + 1, i)) first max ans, then maximize i 
    vector<ll> p(n + 1, 0); 
    for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i]; 

    vector<pair<int, int>> best(n, {1, -1}); 

    for (int i = 0; i < n; ++i) {
        if (i > 0) best[i] = max(best[i], best[i - 1]); 

        // cout << "! proc i " << i << ' ' << best[i].first << ' ' << best[i].second << '\n'; 

        ll b = p[i + 1] - p[best[i].second + 1]; 
        // cout << "b " << b << '\n';
        if (p[n] - p[i + 1] >= b) {
            int lo = i + 1, hi = n - 1; 
            while (lo < hi) {
                int md = (hi + lo) / 2; 
                if (p[md + 1] - p[i + 1] >= b) {
                    hi = md; 
                } else {
                    lo = md + 1; 
                }
            }
            // cout << "next " << lo << '\n';

            best[lo] = max(best[lo], {best[i].first + 1, i}); 
        }
    }

    return best[n - 1].first; 
}

ll slow(int n, vector<ll> & a) {
    ll ans = 0; 
    for (int i = 0; i < (1 << (n - 1)); ++i) {
        ll c = 0, last = 1, cnt = 0; 
        for (int j = 0; j < n; ++j) {
            c += a[j]; 
            if ((1 << j) & i) {
                if (c >= last) {
                    last = c; 
                    c = 0; 
                    cnt++; 
                } else {
                    cnt = -n; 
                    break; 
                }
            }
        }
        if (c >= last) cnt++; 
        ans = max(ans, cnt); 
    }
    return ans; 
}

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

    int n; cin >> n; 
    vector<ll> a(n); 
    for (auto & x: a) cin >> x; 
    cout << solve(n, a) << '\n';
    // int t; 
    // cin >> t; 
    // for (int i = 0; i < t; ++i) {
    //     int n; 
    //     cin >> n; 
    //     vector<ll> a(n); 
    //     for (auto & x: a) cin >> x; 
    //     ll x = solve(n, a), y = slow(n, a); 

    //     cout << x << '\n';
    //     if (x != y) {
    //         cout << "! " << x << ' ' << y << '\n';
    //         for (auto z: a) cout << z << '\n';
    //     }
    // }

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27