Advertisement
a53

Comisia

a53
Oct 2nd, 2021
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. //Soltuie Iacob Tudor O(nlogn) cu RMQ.
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. ifstream fin("comisia.in");
  5. ofstream fout("comisia.out");
  6. long long n,s[200005],dp[200005][20],l[200005],mn(1e18+7);
  7. long long qr(long long st,long long dr){
  8. long long lg(l[dr-st+1]);
  9. return max(dp[st][lg],dp[dr-(1<<lg)+1][lg]);
  10. }
  11. void sim(long long p){
  12. long long l(dp[p][0]),pi(p);
  13. while(p-pi+1<l&&l+pi-1<=n){
  14. p=pi+l-1;
  15. l=qr(pi,p);
  16. }
  17. if(p-pi+1==l&&pi+l-1<=n)mn=min(mn,s[p]-s[pi-1]);
  18. }
  19. int main(){
  20. fin>>n;
  21. for(long long i=1;i<=n;i++)fin>>dp[i][0];
  22. for(long long i=1;i<=n;i++)fin>>s[i],s[i]+=s[i-1];
  23. for(long long i=2;i<=n;i++){
  24. l[i]=l[i-1];
  25. if(!(i&(i-1)))l[i]++;
  26. }
  27. for(long long i=1;(1<<i)<=n;i++){
  28. for(long long j=1;j+(1<<i)-1<=n;j++){
  29. dp[j][i]=max(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
  30. }
  31. }
  32. for(long long i=1;i<=n;i++)sim(i);
  33. fout<<mn;
  34. return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement