Submission #628088

#	Time	Username	Problem	Language	Result	Execution time	Memory
628088		nttt	Bigger segments (IZhO19_segments)	C++14	0 / 100	0 ms	212 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define task "name"

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 5e5 + 7;
const int BASE = 10;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int n;
int a[N];
ll pre[N], presum = 0;

bool ok(int pos, int x)
{
    if(pre[x] - pre[pos] >= presum) return 1;
    return 0;
}
int cnp(int pos, int l, int r)
{
    while(true)
    {
        if(l == r) return l;
        if(r - l == 1) return (ok(pos, l) ? l : r);
        int mid = (l + r) / 2;
        if(ok(pos, mid)) r = mid;
        else l = mid;
    }
}
void Solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];

    pre[n + 1] = loo;
    int ans = 1;
    if(a[1] <= a[2])
    {
        presum = pre[1];
        int p = 1;
        int cnt = 1;
        while(p < n + 1)
        {
            int k = cnp(p, p + 1, n + 1);
            if(k >= n + 1) break;
            presum = pre[k] - pre[p];
            p = k;
            cnt++;
        }
        maximize(ans, cnt);
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            presum = pre[i];
            int p = i;
            int cnt = 1;
            while(p < n + 1)
            {
                int k = cnp(p, p + 1, n + 1);
                if(k >= n + 1) break;
                presum = pre[k] - pre[p];
                p = k;
                cnt++;
                if(cnt + (n - p) <= ans) break;
            }
            maximize(ans, cnt);
        }
    }

    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    int T = 1;
    //cin >> T;
    while(T--)
    {
        Solve();
    }

    return 0;
}

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