This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+3;
long long i,j,p,q,n,m,k;
long long uk,dp[maxn],pref[maxn],a[maxn],pos[maxn],l,r,mid;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
pref[i]=pref[i-1]+a[i];
}
for(i=1;i<=n;i++)
{
pos[i] = max(pos[i],pos[i-1]);
p = pref[i]-pref[pos[i]];
dp[i] = dp[pos[i]]+1;
l = i;
r = n;
q = 0;
while(l<=r)
{
mid = (l+r)/2;
if(pref[mid]-pref[i]>=p)
r = mid-1,q=mid;
else l = mid+1;
}
pos[q] = i;
}
cout<<dp[n]<<endl;
return 0;
}
///ketevan is a legend
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |