比赛 2008haoi模拟训练3 评测结果 ATAAATTTTT
题目名称 阶梯教室设备利用 最终得分 40
用户昵称 SMXX 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-04-24 11:16:38
显示代码纯文本
program rez;
var
f1,f2:text;
max,sum,n,i,j:integer;
a:array[0..10000,1..3]of integer;
b:array[0..10000]of boolean;
t:array[0..30000]of boolean;
procedure qsort(l,r:integer);
var i,j,mid,tm:integer;
begin
i:=l;j:=r;mid:=a[(i+j)div 2,1];
repeat
 while a[i,1]<mid do inc(i);
 while a[j,1]>mid do dec(j);
 if i<=j then begin tm:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=tm;
                   tm:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=tm;
                    tm:=a[i,3];a[i,3]:=a[j,3];a[j,3]:=tm;
                     inc(i);dec(j);end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function find(i:integer):boolean;
var g,h:integer;
begin
for g:=a[i,1] to a[i,2] do
    if t[g] then begin find:=false;exit;end;
find:=true;
end;
procedure def(i:integer);
var j,k:integer;
begin
while i<=n do begin
 if (not(b[i]))and find(i)then begin b[i]:=true; sum:=sum+a[i,3];
                                     for j:=a[i,1] to a[i,2] do t[j]:=true;
                                      if i<n then def(i+1);
                                      if sum>max then max:=sum;
                                      b[i]:=false;sum:=sum-a[i,3];
                                      for j:=a[i,1]to a[i,2]do t[j]:=false;
                                      inc(i);
                                     end
                          else inc(i);
              end;
end;

begin
assign(f1,'rez.in');
assign(f2,'rez.out');
reset(f1);
rewrite(f2);
readln(f1,n);
max:=0;
sum:=0;
for i:= 1to n do begin
 readln(f1,a[i,1],a[i,2]);
  a[i,3]:=a[i,2]-a[i,1];
  if a[i,1]<>0 then inc(a[i,1]);
   end;
qsort(1,n);
def(1);
writeln(f2,max);
close(f1);
close(f2);
end.