比赛 20140414 评测结果 C
题目名称 登机 最终得分 0
用户昵称 hzoi_zyl 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2014-04-14 11:15:12
显示代码纯文本
var
   i,j,k:longint;
   bh,wz,s,t:array[1..200000]of int64;
   ans1,x,ans:int64;
   v:array[1..200050]of boolean;
   n:longint;

procedure swap(var x,y:longint);
var t:longint;
begin
     t:=x;x:=y;y:=t;
end;

procedure swap(var x,y:int64);
var t:int64;
begin
     t:=x;x:=y;y:=t;
end;

function max(x,y:int64):int64;
begin
     if x>y then exit(x);exit(y);
end;

function max(x,y:longint):longint;
begin
     if x>y then exit(x);exit(y);
end;

procedure qsort(l,r:longint);
var i,j:longint;x:int64;
begin
     i:=l;j:=r;x:=s[(l+r)shr 1];
     repeat
           while s[i]<x do inc(i);
           while s[j]>x do dec(j);
           if i<=j then
           begin
                swap(s[i],s[j]);
                swap(t[i],t[j]);
                swap(bh[i],bh[j]);
                swap(wz[i],wz[j]);
                inc(i);
                dec(j);
           end;
     until i>j;
     if i<r then qsort(i,r);
     if j>l then qsort(l,j);
end;

begin
     assign(input,'boarding.in');
     reset(input);
     assign(output,'boarding.out');
     rewrite(output);

     readln(n);
     for i:=1 to n do
     begin
           readln(s[i],t[i]);
           bh[i]:=i;
           wz[i]:=i-n;
     end;
     fillchar(v,sizeof(v),true);
     ans:=0;
     qsort(1,n);
     for i:=1 to n do
     if v[i] then
     begin
          x:=s[i]-wz[i];
          inc(ans,x);
          ans1:=t[i];
          v[i]:=false;
          for j:=1 to n do
          if v[j] then
          begin
               inc(wz[j],x);
               if wz[j]=s[j] then
               begin
                    ans1:=max(ans1,t[j]);
                    v[j]:=false;
               end;
          end;
          inc(ans,ans1);
     end;
     writeln(ans);

     close(input);close(output);
end.