NKBUS - Bus

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=200001;
var
  n,m,sl:int64;
  a,d,ind,l,r:array[1..MAXN] of int64;
procedure inp;
var
  f:text;
  i,j,k:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m); sl:=0;
  for i:=1 to n do
    begin
      read(f,d[i],k);
      for j:=1 to k do
        begin
          inc(sl);
          read(f,a[sl]); ind[sl]:=i;
        end;
    end;
  close(f);
end;
procedure solve;
var
  i:longint;
begin
  l[1]:=0; for i:=2 to n do l[i]:=l[i-1]+d[i-1];
  r[n+1]:=0; for i:=n downto 1 do r[i]:=r[i+1]+d[i];
  for i:=1 to sl do a[i]:=max(l[ind[i]],a[i])+r[ind[i]];
end;
procedure swap(var a,b:int64); inline;
var
  temp:int64;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:int64); inline;
var
  i,j,mid:int64;
begin
  i:=l; j:=r; mid:=a[(l+r) shr 1];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
      begin
        swap(a[i],a[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 ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,a[m]);
  close(f);
end;
begin
  inp;
  solve;
  sort(1,sl);
  if m>sl then m:=sl;
  ans;
end.

Download