Submission #685071

#	Time	Username	Problem	Language	Result	Execution time	Memory
685071		gagik_2007	Bigger segments (IZhO19_segments)	C++17	27 / 100	1584 ms	244088 KiB

segments

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 3007;
ll n, m, k;
ll a[N];
ll dp[N][N];
ll pf[N];
ll dppf[N];
ll t[N][4 * N];

void build(int v, int tl, int tr, int i) {
    if (tl == tr) {
        t[i][v] = 0;
    }
    else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm, i);
        build(2 * v + 1, tm + 1, tr, i);
        t[i][v] = max(t[i][2 * v], t[i][2 * v + 1]);
    }
}

void update(int v, int tl, int tr, int ind, ll val, int i) {
    if (tl == tr) {
        t[i][v] = val;
    }
    else {
        int tm = (tl + tr) / 2;
        if (ind <= tm) {
            update(2 * v, tl, tm, ind, val, i);
        }
        else {
            update(2 * v + 1, tm + 1, tr, ind, val, i);
        }
        t[i][v] = max(t[i][2 * v], t[i][2 * v + 1]);
    }
}

ll get_max(int v, int tl, int tr, int l, int r, int i) {
    if (l > r)return -MOD;
    if (tl == l && tr == r) {
        return t[i][v];
    }
    else {
        int tm = (tl + tr) / 2;
        return max(get_max(2 * v, tl, tm, l, min(r, tm), i),
            get_max(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, i));
    }
}

ll pref(int l, int r) {
    if (l == 0)return pf[r];
    return pf[r] - pf[l - 1];
}

int find_ind(ll sum, int j) {
    if (a[j] > sum) {
        return -1;
    }
    int l = 0, r = j;
    while (r > l) {
        int mid = (l + r) / 2;
        if (pref(mid, j) <= sum) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i == 0)pf[i] = a[i];
        else pf[i] = pf[i - 1] + a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = 1;
            }
            else {
                int p = find_ind(pref(j, i), j - 1);
                if (p == -1) {
                    dp[i][j] = -MOD;
                }
                else {
                    //cout << p << ", " << j - 1 << ": ";
                    dp[i][j] = get_max(1, 0, n - 1, p, j - 1, j - 1) + 1;
                }
            }
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
        build(1, 0, n - 1, i);
        for (int j = 0; j <= i; j++) {
            update(1, 0, n - 1, j, dp[i][j], i);
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[n - 1][i]);
    }
    cout << ans << endl;
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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