Submission #1006271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006271		christinelynn	Bigger segments (IZhO19_segments)	C++17	73 / 100	12 ms	3676 KiB

segments

#include <bits/stdc++.h>
using namespace std; 
#define int long long 
#define ld long double
#define fi first 
#define se second 
#define pb push_back
#define pii pair<int,int>
#define piii pair<pair<int,int>,pair<int,int>>

int a[100005]; 
int pref[100005], dp[100005], bef[100005]; 
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    int n; cin >> n; 
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
        pref[i] = pref[i-1] + a[i]; 
    }
    a[n+1] = 1e18; 
    int ans = 0; 
    for(int i = 1; i <= n; i++){
        bef[i] = max(bef[i], bef[i-1]); 
        dp[i] = dp[bef[i]] + 1; 
        ans = max(ans, dp[i]); 
        int l = 1, r = n + 1, ret = -1;
        while(l <= r){
            int mid = (l+r)/2;
            if(pref[mid] >= (2 * pref[i]) - pref[bef[i]]){
                r = mid - 1; 
                ret = mid; 
            }
            else{
                l = mid + 1; 
            }
        }
        bef[ret] = i; 
    }
    cout << ans << endl; 
}

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