Untitled
unknown
plain_text
a month ago
946 B
1
Indexable
Never
#include<bits/stdc++.h> using namespace std; int sum(int i,int j,int *prf) { if (i==0) return prf[j]; return prf[j]-prf[i-1]; } void solve() { int n; cin>>n; vector<int>v(n); for (auto &x:v)cin>>x; int prf[n]; prf[0]=v[0]; for (int i=1;i<n;++i)prf[i]=prf[i-1]+v[i]; set<int>s; int output=0; for (int i=1;i<n;++i) { if(v[i]<=v[i-1]) { output++; s.insert(i-1); } else { while(!s.empty()) { int r=*(--s.end()); s.erase(r); if (sum(r,i-1,prf)>=v[i]) { output+=(i-r); s.insert(r); break; } } } } cout<<output; } signed main() { #ifndef ONLINE_JUDGE freopen("Error.txt", "w", stderr); #endif int t=1; while(t--)solve(); }
Leave a Comment