比赛 20101101 评测结果 AWWWWEEEEE
题目名称 奇怪的监狱 最终得分 10
用户昵称 digital-T 运行时间 0.016 s
代码语言 Pascal 内存使用 0.17 MiB
提交时间 2012-11-05 11:36:09
显示代码纯文本
var
p,q,i,j,t,n,ans,h:longint;
f,w:array[1..100]of longint;
k:array[1..100]of boolean;
procedure quick(l,r:longint);
var x,y,z,zz:longint;
begin
x:=l;y:=r;z:=f[(x+y)div 2];
repeat
while f[x]<z do inc(x);
while f[y]>z do dec(y);
if x<=y then
 begin
  zz:=f[x];
  f[x]:=f[y];
  f[y]:=zz;
  inc(x);
  dec(y);
 end;
until i>j;
if l<=y then quick(l,y);
if x<=r then quick(x,r);
end;

begin
assign(input,'prison.in');reset(input);
assign(output,'prison.out');rewrite(output);
read(p,q);
fillchar(k,sizeof(k),true);
for i:=1 to q do
 begin
  read(j);
  k[j]:=false;
 end;
j:=1;
for i:=1 to p do
 if k[i]then inc(f[j]) else inc(j);
n:=j;
//_____________________________
for i:=n downto 2 do
 begin
  h:=1;
  for j:=2 to i-1 do
   if f[h]+f[h+1]>f[j]+f[j+1] then
    h:=j;
  f[h]:=f[h]+f[h+1]; ans:=ans+f[h];
  for j:=h+1 to i-1 do f[j]:=f[j+1];
 end;
//_____________________________
for i:=q-1 downto 1 do ans:=ans+i;
write(ans);






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