fork download
copy 
  1. #include <bits/stdc++.h> 
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. #define pb  push_back  
  8. #define ll  int
  9. #define el  "\n"
  10. #define alla(a,n)  a+1,a+n+1
  11. #define fi first
  12. #define se second
  13. #define all(v)  v.begin(),v.end()
  14. #define fu(i,a,b)  for(ll i=a;i<=b;i++)
  15. #define fud(i,a,b)  for(ll i=a;i>=b;i--)
  16.  
  17. const ll MOD=1e9+7 ;//1234567891;
  18. const ll inf=1e18;
  19. const ll base = 311;
  20. const ll N=1e6+5;
  21. const ll N1=1e3+5;
  22. /*🥑*/
  23. template <class T> bool minimize(T &x, T y){return (x > y ? x = y, 1 : 0);}
  24. template <class T> bool maximize(T &x, T y){return (x < y ? x = y, 1 : 0);}
  25. template <class T> void add(T &x, ll y){x += y; if(x >= MOD) x -= MOD;}
  26. template <class T> void sub(T &x, T y){x -= y; if(x < 0) x += MOD;}
  27. /*v*/
  28. int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1},
  29.     dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
  30.  
  31. ll n;
  32. long long S,s[N];
  33. ll a[N],nxt[N],dd[N],cc[N],res[N];
  34. signed main(void)
  35. {
  36.     #define TASK  "4"
  37.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
  38.     if(fopen(TASK".INP","r"))
  39.     {
  40.         freopen(TASK".inp" ,"r",stdin) ; freopen(TASK".out" ,"w",stdout);
  41.     }
  42.  
  43.     cin>>n>>S;
  44.     fu(i,1,n) cin>>a[i],s[i]=s[i-1]+a[i];
  45.     long long ans=0;
  46.     fu(i,1,n)
  47.     {
  48.         ll j=upper_bound(s+i,s+n+1,s[i-1]+S)-s;
  49.         nxt[i]=j;
  50.     }
  51.     fud(i,n,1)
  52.     {
  53.         ll cur=i,cnt=0;
  54.         ll nxt_pos=nxt[cur];
  55.         cc[i]=cc[nxt_pos]+1;
  56.         res[i]=res[nxt_pos]+n-i+1;
  57.         ans+=res[i];
  58.  
  59.     }
  60.     cout<<ans;
  61.  
  62.     // số MOD bro
  63.     cerr<<el<<"Time: "<<0.001*clock()<<"s"<<el;return 0;
  64. }
Success #stdin #stdout #stderr 0s 5264KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time: 4.225s
https://ideone.com/L7xItJ
language:
C++14 (gcc 8.3)
created:
153 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!