Cod sursa(job #18574)

Utilizator andrei_blanaruAndrei Blanaru andrei_blanaru Data 18 februarie 2007 12:39:37
Problema Ghiozdan Scor 0
Compilator fpc Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.47 kb
{ghiozdan}
var n,g,ss,sd,ssum:longint;
    a:array [1..20005] of integer;

procedure citire;
var i:longint;
begin
  assign(input,'ghiozdan.in');
  reset(input);
  readln(n,g);
  for i:=1 to n do
    readln(a[i]);
  close(input);
end;

procedure Sort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i] > x do i := i + 1;
    while x > a[j] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

procedure prel;
var st,dr:integer;
    s:longint;
begin
  s:=a[1];
  st:=1; dr:=1;
  while dr<=n do
    begin
      if (s+a[dr+1]>g)or(dr=n)
        then  begin
                if (s>ssum)or(s=ssum)and(dr-st<sd-ss)
                  then  begin
                          ssum:=s;
                          ss:=st;
                          sd:=dr;
                        end;
                while s+a[dr+1]>g do
                  begin
                    dec(s,a[st]);
                    inc(st);
                  end;
              end;
      inc(dr);
      inc(s,a[dr]);
    end;
end;

procedure scrie;
var i:integer;
begin
  assign(output,'ghiozdan.out');
  rewrite(output);
  writeln(ssum,' ',sd-ss+1);
  for i:=ss to sd do
    writeln(a[i]);
  close(output);
end;

begin
  citire;
  sort(1,n);
  prel;
  scrie;
end.