Submission #868001

#TimeUsernameProblemLanguageResultExecution timeMemory
868001sleepntsheepBigger segments (IZhO19_segments)C++17
0 / 100
0 ms348 KiB
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()
int n, a[N];

int ok(int m)
{
    ll c = 0, last = 0, cur = 0;
    for (int i = 1; i <= n; ++i)
    {
        cur += a[i];
        if (cur >= last) last = cur, ++c, cur = 0;
        if (c == m) return 1;
    }
    return 0;
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r)/2;
        if (ok(m)) l=m+1;
        else r=m-1;
    }
    cout << l-1;

    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...