Submission #1307196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307196		jahongir	Bigger segments (IZhO19_segments)	C++20	27 / 100	683 ms	235148 KiB

segments

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


bool mb;
const int mxn = 3001, mxa = 2e7;
const ll lim = 3e12;

int st[mxa], pl[mxa], pr[mxa], node = 0;
int root[mxn];
ll pref[mxn];


bool md;

int update(int cur, ll l, ll r, ll k, int val){
    if(!cur) cur = ++node;
    if(l==r){st[cur]=val; return cur;}
    ll m = (l+r)>>1;
    if(k <= m) pl[cur] = update(pl[cur],l,m,k,val);
    else pr[cur] = update(pr[cur],m+1,r,k,val);
    st[cur] = max(st[pl[cur]],st[pr[cur]]);
    return cur;
}

int get(int cur, ll l, ll r, ll s, ll e){
    if(r < s || l > e || !cur) return -1e9;
    if(s <= l && r <= e) return st[cur];
    ll m = (l+r)>>1;
    return max(get(pl[cur],l,m,s,e),get(pr[cur],m+1,r,s,e));
}



void solve(){



    st[0] = -1e9;

    int n; cin >> n;
    assert(n <= 3000);

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

        root[i] = update(0,1,lim,pref[i],1);
        for(int j = 1; j < i; j++){
            int r = get(root[j],1,lim,1,pref[i]-pref[j]);
            if(r != -1e9) root[i] = update(root[i],1,lim,pref[i]-pref[j],r+1);
        }
    }

    cout << get(root[n],1,lim,1,pref[n]);

}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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