VPARTSUM - Tổng bộ phận

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
      maxn=100100;
var n,z,k,re,num:longint;
    a:array[0..maxn*2] of longint;
    b,c,d:array[0..maxn] of longint;

procedure rf;
var x,i:longint;
begin
     read(n,k,z);
     re:=z-1;
     for i:=1 to n do
     begin
          read(x);
          x:=x mod z;
          if x>=k then re:=min(re,x);
          a[i]:=(a[i-1]+x) mod z;
          d[i]:=i;
     end;
end;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=d[(j+i) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (d[i]<y)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (d[j]>y)) do j:=j-1;
           if i<=j then
           begin
               t:=a[i]; a[i]:=a[j]; a[j]:=t;
               t:=d[i]; d[i]:=d[j]; d[j]:=t;
               i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(val,l:longint):longint;
var r,m,i:longint;
begin
     r:=l+num;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if a[m]<val then l:=m+1
          else r:=m-1;
     end;
     for i:=m-1 to m+1 do
         if (i>=0) and (i<=num*2+1) and (a[i]>=val) then exit(i mod (num+1));
end;

procedure pr;
var i,x:longint;
begin
     sort(0,n);
     num:=0;
     for i:=1 to n do
         if a[i]>a[num] then
         begin
              num:=num+1;
              a[num]:=a[i];
              b[num]:=d[i];
              c[num-1]:=d[i-1];
         end;
     c[num]:=d[n];
     for i:=0 to num do a[num+1+i]:=a[i]+z;
     for i:=0 to num do
     begin
          x:=bs(a[i]+k,i);
          while ((a[x]-a[i]+z) mod z<re) do
          begin
               if b[i]<c[x] then
               begin
                    re:=(a[x]-a[i]+z) mod z;
                    break;
               end;
               x:=(x+1) mod (num+1);
          end;
          if re=k then break;
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download