제출 #1139852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139852		andrewp	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	328 KiB

segments

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>   
#define all(x) x.begin(), x.end()
#define sz(a) ((int)a.size())
inline ll readint() {ll x; cin >> x; return x;}    
const int N=5e5+5;    

int n, a[N];
ll ps[N];

int main () {   
    ios::sync_with_stdio(false), cin.tie(0);  
        
    n=readint();
    for (int i=1; i<=n; i++) {
        a[i]=readint();
        ps[i]=ps[i-1]+a[i];
    }
    int ans=1;
    for (int j=1; j<=n; j++) {
        int i=j+1, curr=1; 
        ll sum=a[1];
        while (i<=n) {
            int lo=i, hi=n, nxt=-1;
            while (lo<=hi) {
                int mid=(lo+hi)/2;
                if (ps[mid]-ps[i-1]>=sum) {
                    nxt=mid;
                    hi=mid-1;
                }
                else 
                    lo=mid+1;
            }    
            if (nxt==-1) 
                break;
            curr++;
            sum=ps[nxt]-ps[i-1];
            i=nxt+1;
        }
        ans=max(ans, curr);
    }
    cout << ans << '\n';
}

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