Submission #154969

#	Time	Username	Problem	Language	Result	Execution time	Memory
154969		Pankin	Bigger segments (IZhO19_segments)	C++14	13 / 100	3 ms	504 KiB

segments

#include <bits/stdc++.h>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define con continue
#define pii pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const ll mod = 1000000007;
const ll P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;

vector< pair<ll, ll> > dir = {
    {
        -1, 0
    },
    {
        0, 1
    },
    {
        1, 0
    },
    {
        0, -1
    }
};

bool valid(ll x, ll y, ll n, ll m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

const ll N = 500000 + 5;
ll dp[N], col[N], a[N], pref[N], n;

signed main() {
    fast_io;

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = a[i] + pref[i - 1];
    }

    for (ll i = 1; i <= n; i++) {
        ll l = 1, r = i;
        while(l != r) {
            ll mid = (l + r + 1) / 2;
            if (pref[i] - pref[mid - 1] >= dp[mid - 1])
                l = mid;
            else
                r = mid - 1;
        }
        col[i] = col[l - 1] + 1;
        dp[i] = pref[i] - pref[l - 1];
    }
    cout << col[n];

    return 0;
}

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