VPARTSUM - Tổng bộ phận
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
FINP='';
FOUT='';
MAXN=1000111;
var
c,ln,a,sum:array[0..MAXN] of int64;
best,sl,n,p,k:int64;
test:longint;
f1,f2:text;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n,k,p);
fillchar(a,sizeof(a),0);
fillchar(sum,sizeof(sum),0);
fillchar(ln,sizeof(ln),0);
fillchar(c,sizeof(c),0);
for i:=1 to n do read(f1,a[i]);
for i:=1 to n do sum[i]:=(sum[i-1]+a[i]) mod p;
sum[n+1]:=0;
end;
procedure swap(var a,b:int64); inline;
var
temp:int64;
begin
temp:=a; a:=b; b:=temp;
end;
var
mid:int64;
procedure sort(l,r:int64); inline;
var
i,j:int64;
begin
mid:=c[l+random(r-l+1)]; i:=l; j:=r;
repeat
while c[i]<mid do inc(i);
while c[j]>mid do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure init;
var
i:longint;
begin
for i:=1 to n+1 do c[i]:=sum[i];
sort(1,n+1);
sl:=1;
for i:=2 to n+1 do
if c[i]>c[sl] then
begin
inc(sl);
c[sl]:=c[i];
end;
end;
function get(u:int64):int64; inline;
var
kq,v:int64;
begin
if u<=0 then exit(0);
kq:=ln[u];
v:=u-u and (-u);
if v>0 then kq:=max(kq,get(v));
exit(kq);
end;
procedure update(u,k:int64); inline;
var
v:int64;
begin
ln[u]:=max(ln[u],k);
v:=u+u and (-u);
if v<=sl then update(v,k);
end;
function find(x:int64):int64; inline;
var
l,r,kq:int64;
begin
l:=1; r:=sl; kq:=0;
repeat
mid:=(l+r)>>1;
if c[mid]<=x then
begin kq:=mid; l:=mid+1; end
else r:=mid-1;
until l>r;
exit(kq);
end;
procedure solve;
var
u,temp:int64;
i:longint;
begin
best:=maxlongint;
for i:=1 to n do
begin
if sum[i]>=k then
begin
u:=find(sum[i]-k);
best:=min(best,sum[i]-get(u));
end;
u:=find(sum[i]+p-k);
temp:=get(u);
if temp>sum[i] then best:=min(best,sum[i]-temp+p);
u:=find(sum[i]);
update(u,sum[i]);
end;
end;
procedure ans;
begin
writeln(f2,best);
end;
begin
openF;
// readln(f1,test);
test:=1;
for test:=1 to test do
begin
inp;
init;
solve;
ans;
end;
closeF;
end.