Submission #628764

#	Time	Username	Problem	Language	Result	Execution time	Memory
628764		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 = 1e6 + 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, delta = 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;
    }
}
int calc(int l, int r)
{
    int ans = 1;
    delta = pre[l - 1];
    for(int i = l; i <= r; i++)
    {
        presum = pre[i] - delta;
        int p = i;
        int cnt = 1;
        while(p < r + 1)
        {
            int k = cnp(p, p + 1, r + 1);
            if(k >= r + 1) break;
            presum = pre[k] - pre[p];
            p = k;
            cnt++;
        }
        maximize(ans, cnt);
    }
    return ans;
}
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];
    vector<int> pos;
    pos.pb(1);
    for(int i = 2; i <= n; i++)
    {
        if(a[i] >= pre[i - 1] - pre[pos[pos.size() - 1] - 1]) pos.pb(i);
    }
    pos.pb(n + 1);
    pre[n + 1] = loo;
    int ans = 0;
    for(int i = 1; i < pos.size(); i++)
        ans += calc(pos[i - 1], pos[i] - 1);
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int T = 1;
    //cin >> T;
    while(T--)
    {
        Solve();
    }
 
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void Solve()':
segments.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 1; i < pos.size(); i++)
      |                    ~~^~~~~~~~~~~~

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