Submission #1220626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220626		M_SH_O	Bigger segments (IZhO19_segments)	C++20	27 / 100	1595 ms	48816 KiB

segments

#include <bits/stdc++.h>
//#include "grader.h"
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/

#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
//#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define all(a) a.begin(), a.end()
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 1000000000000000000
#define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

mt19937 rng(1488);
ll randll(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

/*vvll s1;
vll p;

ll find(ll v) {
    if (p[v] == v) return v;
    return p[v] = find(p[v]);
}

vll unite(ll a, ll b) {
    a = find(a);
    b = find(b);

    if (a == b) return {};
    if (s1[a].size() < s1[b].size()) {
        p[a] = b;
        for (auto i : s1[a]) {
            s1[b].pb(i);

        }
        return s1[a];
    }
    else {
        p[b] = a;
        for (auto i : s1[b]) {
            s1[a].pb(i);

        }
        return s1[b];
    }
}

vll tree1, d, tree;

void push(ll v, ll tl, ll tr) {
    if (tl == tr) return;
    tree1[v*2] += d[v];
    tree1[v*2+1] += d[v];
    d[v*2] += d[v];
    d[v*2+1] += d[v];
    d[v] = 0;
    tree1[v] = tree1[v*2]+tree1[v*2+1];
}

void bt(ll v, ll tl, ll tr, vll& a) {
    if (tl == tr) {
        tree1[v] = tree[v] = a[tl];
        return;
    }

    ll tm = (tl+tr)/2;
    bt(v*2, tl, tm, a);
    bt(v*2+1, tm+1, tr, a);

    tree1[v] = min(tree1[v*2], tree1[v*2+1]);
    tree[v] = max(tree[v*2], tree[v*2+1]);
}

ll get(ll l, ll r, ll v, ll tl, ll tr) {
    if (l <= tl && tr <= r) return tree[v];
    if (tl > r || tr < l) return -INF;

    ll tm = (tl+tr)/2;
    //push(v, tl, tr);
    ll p = get(l, r, v*2, tl, tm), p1 = get(l, r, v*2+1, tm+1, tr);
    return max(p,p1);
}


void update(ll idx, ll val, ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree[v] = val;
        /*d[v] += val;
        push(v, tl, tr);
        return;
    }

    ll tm = (tl+tr)/2;
    //push(v, tl, tr);

    if (idx <= tm)update(idx, val, v*2, tl, tm);
    else update(idx, val, v*2+1, tm+1, tr);

    tree[v] = max(tree[v*2], tree[v*2+1]);
}*/

ll n;
vll a;

ll f(ll k, ll sm, ll add, vll& s, vvll& p, map<pll, ll>& m) {
    if (k == -1) {
        return 0;
    }
    //if (m.find({k, add}) != m.end()) return m[{k, add}];
    if (s[k]+add <= sm) return 1;
    ll l1 = -1, r1 = p[k].size();
    /*while (r1 - l1 > 1) {
        ll x = (l1+r1)/2;
        if (s[k]-p[k][x]+add <= sm) r1 = x;
        else l1 = x;
    }*/
    for (int i = 0; i < p[k].size(); i ++) {
        if (s[k]-p[k][i]+add <= sm) {
            r1 = i;
            break;
        }
    }
    //cout << l1 << ' ' << r1 << endl;
    if (r1 == p[k].size()) return 0;
    if (r1 == p[k].size()-1 && add == 0) return 0;
    ll kl = f(k-1, s[k]-p[k][r1]+add, p[k][r1], s, p, m);
    //if (add != 0) m[{k, add}] = kl;
    return kl;
}

ll solve() {
    vll l(n+7, 0), r(n+7, 0), s(n+7, 0);
    vvll p(n+7);
    p[0].pb(a[0]);
    s[0] = a[0];
    ll k = 0;
    ll sm = 0, pos = 1;
    map<pll, ll> m;

    for (int i = 1; i < n; i ++) {
        if (sm == 0) l[k+1] = i;
        sm += a[i];
        p[k+1].pb(sm);
        ll l1 = -1, r1 = p[k].size();
        //cout << f(k, sm, 0, s, p, m) << endl;
        if (f(k, sm, 0, s, p, m)){
            r[k+1] = i;
            s[k+1] = sm;
            k ++;
            sm = 0;
        }
    }
    return k+1;
}

ll check() {
    vector<vpll> dp(n);
    dp[0].pb({a[0], 1});
    ll sm = a[0];
    for (int i = 1; i < n; i ++) {
        sm += a[i];
        dp[i].pb({sm, 1});
        ll s = 0;
        for (int j = i; j > 0; j --) {
            s += a[j];
            ll maxl = -INF;
            for (auto i1 : dp[j-1]) {
                if (s >= i1.fr) maxl = max(maxl, i1.se);
            }
            dp[i].pb({s, maxl+1});
            //cout << s << ' ' << maxl << endl;
        }
        //cout << endl;
    }
    ll maxl = 0;
    for (auto i : dp[n-1]) {
       // cout << i.fr << ' ' << i.se << endl;
        maxl = max(maxl, i.se);
    }
    return maxl;
}

int main() {
    srand(time(0));
    speed;

    cin >> n;
    a.resize(n);
    for (int i =0 ; i < n; i ++) {
        cin >> a[i];
    }

    cout << check() << endl;
}

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