This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Just try and the idea will come
#include<bits/stdc++.h>
#define ll long long int
#define fr first
#define sc second
using namespace std;
ll pref[500001],i,n,l,r,m,tree[2000001],a[500001];
pair<ll,ll>dp[500001];
void update(int v,int l,int r,int pos,int val){
if(l==pos&&r==pos){
tree[v]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update((v<<1),l,mid,pos,val);
else update((v<<1)+1,mid+1,r,pos,val);
tree[v]=min(tree[(v<<1)],tree[(v<<1)+1]);
}
int get(int v,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return tree[v];
if(r<ql||qr<l)return 1e15;
int mid=(l+r)>>1;
return min(get((v<<1),l,mid,ql,qr),get((v<<1)+1,mid+1,r,ql,qr));
}
int main(){
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld",&pref[i]);
pref[i]+=pref[i-1];
}
for(i=1;i<=n;i++){
for(int j=0;j<i;j++)
if(pref[i]>=a[j])dp[i]={dp[j].fr+1,pref[i]-pref[j]};
a[i]=dp[i].sc+pref[i];
/*l=0,r=i-1;
while(l<r){
m=(l+r+1)>>1;
if(pref[i]>=get(1,0,n,m,i-1))l=m;
else r=m-1;
}
dp[i]={dp[l].fr+1,pref[i]-pref[l]};
update(1,0,n,i,dp[i].sc+pref[i]);*/
}
printf("%lld",dp[n].fr);
}
Compilation message (stderr)
segments.cpp: In function 'int get(int, int, int, int, int)':
segments.cpp:21:28: warning: overflow in implicit constant conversion [-Woverflow]
if(r<ql||qr<l)return 1e15;
^~~~
segments.cpp: In function 'int main()':
segments.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
segments.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&pref[i]);
~~~~~^~~~~~~~~~~~~~~~~
# | 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... |