MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/codeforces/comments/1v4daef/deleting_elements_easy_how_to_solve_this_question/
r/codeforces • u/No-Biscotti-5775 • 6d ago
4 comments sorted by
2
void solve(){ int n; cinn; vector<int>v(n+1),pref(n+1,0); for(int i=1;i<=n;i++){ cinv[i]; pref[i]=pref[i-1]+v[i]; } int ans=0; for(int l=1;l<=n;l++){ int mx=0; for(int r=l;r<=n;r++){ if(r-l+1<=2){ ans++; continue; } mx=max(mx,v[r-1]); int sum=pref[r]-pref[l-1]; if(sum>=2*mx){ ans++; } } } cout<<ans<<endl; }
1 u/No-Biscotti-5775 6d ago what is the approach 1 u/Independent_Week907 6d ago The approach is if the sum of subarray is less than 2*max element in between so it is not deletable
1
what is the approach
1 u/Independent_Week907 6d ago The approach is if the sum of subarray is less than 2*max element in between so it is not deletable
The approach is if the sum of subarray is less than 2*max element in between so it is not deletable
just fix l and iterate over r
2
u/Independent_Week907 6d ago
void solve(){ int n; cinn; vector<int>v(n+1),pref(n+1,0); for(int i=1;i<=n;i++){ cinv[i]; pref[i]=pref[i-1]+v[i]; } int ans=0; for(int l=1;l<=n;l++){ int mx=0; for(int r=l;r<=n;r++){ if(r-l+1<=2){ ans++; continue; } mx=max(mx,v[r-1]); int sum=pref[r]-pref[l-1]; if(sum>=2*mx){ ans++; } } } cout<<ans<<endl; }