Submission #1171497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171497		AlgorithmWarrior	Bigger segments (IZhO19_segments)	C++20	100 / 100	187 ms	37508 KiB

segments

#include <bits/stdc++.h>

using namespace std;

int const MAX=5e5+5;
int n;
int v[MAX];
long long sp[MAX];
struct sol{
    int cnt,ind;
    bool operator<(sol ot){
        if(cnt!=ot.cnt)
            return cnt<ot.cnt;
        return ind<ot.ind;
    }
}dp[MAX];
vector<sol>bonus[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        cin>>v[i];
        sp[i]=sp[i-1]+v[i];
    }
}

long long get_sp(int l,int r){
    return sp[r]-sp[l-1];
}

int bin_search(int id,long long val){
    /// (]
    int st=id,dr=n;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(get_sp(id+1,mij)>=val)
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

int get_dp(){
    int i;
    sol optim={1,0};
    for(i=1;i<=n;++i){
        for(auto bon : bonus[i])
            if(optim<bon)
                optim=bon;
        dp[i]=optim;
        if(get_sp(dp[i].ind+1,i)<=get_sp(i+1,n)){
            int new_id=bin_search(i,get_sp(dp[i].ind+1,i));
            bonus[new_id].push_back({dp[i].cnt+1,i});
        }
    }
    return dp[n].cnt;
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}

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