比赛 |
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.