ac1166.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1166;
const
  maxn=10000;
  maxintervals=199999;
var
  w:array[1..maxn]of longint;
  int:array[boolean,1..maxintervals]of record st,ed:int64;end;
  n,i,p,q,oldcount,count:longint;
  now,last:boolean;
  sp,sq,ep,eq:int64;
procedure qsort(s,t:word);
  var
    p,i,j,tmp:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=w[p];w[p]:=w[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (w[j]>=tmp) do dec(j);
      if i=j then break;w[i]:=w[j];inc(i);
      while (i<j) and (w[i]<=tmp) do inc(i);
      if i=j then break;w[j]:=w[i];dec(j);
    until i=j;
    w[i]:=tmp;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure ins(s,e:int64);
  begin
    if s>int[now,count].ed then begin
      inc(count);with int[now,count] do begin st:=s;ed:=e;end;
    end
    else
      if e>int[now,count].ed then int[now,count].ed:=e;
  end;
begin
  repeat
    read(n);
    for i:=1 to n do read(w[i]);qsort(1,n);
    count:=1;with int[false,1] do begin st:=0;ed:=1;end;
    for i:=1 to n do begin
      now:=odd(i);last:=not now;
      oldcount:=count;count:=1;with int[now,1] do begin st:=0;ed:=1;end;
      p:=1;sp:=int[last,1].st;ep:=int[last,1].ed;
      q:=1;sq:=sp+w[i];eq:=ep+w[i];
      repeat
        if (p<=oldcount) and (sp<sq) then begin
          ins(sp,ep);inc(p);sp:=int[last,p].st;ep:=int[last,p].ed;
        end
        else if q<=oldcount then begin
          ins(sq,eq);inc(q);sq:=int[last,q].st+w[i];eq:=int[last,q].ed+w[i];
        end
        else
          break;
      until false;
    end;

    sp:=-1;
    for i:=1 to count do inc(sp,int[now,i].ed-int[now,i].st);
    writeln(sp);
  until seekeof;
end.