Submission #467023

#TimeUsernameProblemLanguageResultExecution timeMemory
467023TeaTimeBigger segments (IZhO19_segments)C++17
0 / 100
1 ms324 KiB
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 1e6 + 100, INF = 1e9, AM = 2, K = 26;

pair<ll, ll> dp[SZ];
ll n;
vector<ll> vec;

signed main() {
    fastInp;

    cin >> n;
    vec.resize(n);
    vector<ll> pref(1);
    for (auto& c : vec) {
        cin >> c;
        pref.push_back(pref.back() + c);
    }

    ll i2 = 0;
    dp[1] = { 1, vec[0] };
    ll ans = 1;
    for (int i = 2; i <= n; i++) {
        while (i2 + 1 != i && pref[i] - pref[i2 + 1] >= dp[i2 + 1].second) {
            i2++;
        }
        dp[i].second = pref[i] - pref[i2];
        dp[i].first = dp[i2].first + 1;
        ans = max(ans, dp[i].first);
    }

    cout << ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...