Submission #1321377

#TimeUsernameProblemLanguageResultExecution timeMemory
1321377maomaoBigger segments (IZhO19_segments)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,s,n) for(int i=s;i<=n;i++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define eb emplace_back
#define fi first
#define se second
#define tup pair<int, pii>


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n; cin>>n;
    vi a(n+5,0), p(n+5,0);
    rep(i,1,n) {
		cin>>a[i];
		p[i] = p[i-1] + a[i];
	}
	int ans = 1;
	rep(i,1,n) {
		int cnt = 1;
		int l=i+1;
		int cur = p[i];
		while(l<=n) {
			int le=l, ri=n;
			int res = 0;
			while(le<=ri) {
				int mi=(le+ri)>>1;
				if(p[mi]-p[l-1]>=cur) {
					res=mi; ri=mi-1;
				} else le=mi+1;
			}
			if(res==0) break;
			cur = p[res]-p[l-1];
			l=res+1;
			cnt++;
		}
		ans = max(ans, cnt);
	}
	cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...