Submission #155170

#	Time	Username	Problem	Language	Result	Execution time	Memory
155170		Pankin	Bigger segments (IZhO19_segments)	C++14	100 / 100	267 ms	49388 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 + 50;
ll dp[N], col[N], a[N], pref[N], n;

set<pii> st;

signed main() {
    fast_io;

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

    ll curmx = 0;
    for (ll i = 1; i <= n; i++) {
        while(!st.empty() && st.begin()->fs <= pref[i]) {
            curmx = max(curmx, st.begin()->sc);
            st.erase(st.begin());
        }
        dp[i] = pref[i] - pref[curmx];
        col[i] = col[curmx] + 1;
        st.insert(mp(dp[i] + pref[i], i));
    }
    cout << col[n];

    return 0;
}

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