Submission #977062

#	Time	Username	Problem	Language	Result	Execution time	Memory
977062		0pt1mus23	Bigger segments (IZhO19_segments)	C++14	100 / 100	75 ms	16220 KiB

segments

#pragma GCC optimize ("inline","03")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define ins insert
#define pb push_back
#define int long long
#define endl '\n'
/*
    m : 11059739 -> l ~23
    p : 4567896467
*/
const int mod =  1e9 +7, sze=2*1e5,inf=LLONG_MAX, prime = 2333;


void gkd(){
    int n;
    cin>>n;
    vector<int> ps(n+1);
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        ps[i]+=ps[i-1]+arr[i];
    }
    vector<int> dp(n+10),from(n+10);
    for(int i=1;i<=n;i++){
        from[i]=max(from[i],from[i-1]);
        dp[i]=dp[from[i]]+1;
        int t= lower_bound(all(ps),ps[i]*2 - ps[from[i]]) -ps.begin();
        // cout<<t<<" -> "<<i<<" "<<dp[i]<<" ! "<<ps[i]*2 <<" "<< ps[from[i]]<<endl;
        from[t]=i;
    }
    cout<<dp[n]<<endl;

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);  

    int tt=1; 
    // cin>>tt;
    while(tt--) gkd();
    
    return 0;
}

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