Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var s:array[0..1000000] of int64;
- a:array[1..1000000] of longint;
- n,m,i:longint;
- l,r,ans:int64;
- procedure qs(m,t:longint);
- var i,j,w,x,ind:longint;
- begin
- i:=m;
- j:=t;
- randomize;
- ind:=m+random(t-m+1);
- x:=s[ind];
- repeat
- while s[i]<x do inc(i);
- while s[j]>x do dec(j);
- if i<=j then begin
- w:=s[i];
- s[i]:=s[j];
- s[j]:=w;
- inc(i);
- dec(j);
- end;
- until i>j;
- if m<j then qs(m,j);
- if i<t then qs(i,t);
- end;
- begin
- assign(input,'input.txt');
- assign(output,'output.txt');
- reset(input);
- rewrite(output);
- readln(n,m);
- ans:=0;
- for i:=1 to n do
- read(a[i]);
- s[0]:=1;
- for i:=1 to n do
- s[i]:=s[i-1]+a[i];
- qs(0,n);
- l:=0;
- r:=0;
- for i:=0 to n do begin
- while s[l]-s[i]>m do inc(l);
- while (r<=n) and (s[r]-s[i]<=m) do inc(r);
- ans:=ans+(l+(n+1-r));
- end;
- writeln(ans);
- close(input);
- close(output);
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement