状态: Unaccepted
测评机： Xeost[5]
得分： 70分
提交日期： 2011-10-9 15:21:00
有效耗时： 2922毫秒
RQNOJ近期在线比赛列表
RQNOJ十月份月赛 时间:2011-10-21 19:00:00 [报名]
测试结果1: 选手程序运行超过时限
测试结果2: 选手程序无输出
测试结果3: 选手程序无输出
测试结果4: 通过本测试点|有效耗时688ms
测试结果5: 通过本测试点|有效耗时391ms
测试结果6: 通过本测试点|有效耗时359ms
测试结果7: 通过本测试点|有效耗时375ms
测试结果8: 通过本测试点|有效耗时359ms
测试结果9: 通过本测试点|有效耗时375ms
测试结果10: 通过本测试点|有效耗时375ms
program noip2002t4;
const nn=51;mm=501;max=16843009;
type
re=record
x,y,fx,fy:longint;
end;
var
n,i,hm,lm,j,k,ans:longint;
h,l,y,x:array[0..nn]of longint;
map:array[0..nn,0..nn]of boolean;
s:array[0..nn,0..nn]of longint;
d:array[0..nn]of re;
f:array[0..nn,0..nn,0..nn,0..nn,1..4]of longint;
procedure getdata;
begin
readln(n,k);
for i:=1 to n do with d[i] do readln(x,y);
end;
procedure sortx;
var i,j:longint;t:re;
begin
for i:=1 to n-1 do
for j:=i to n do
if (d[i].x>d[j].x)or((d[i].x=d[j].x)and(d[i].y>d[j].y)) then
begin t:=d[i];d[i]:=d[j];d[j]:=t;end;
end;
procedure sorty;
var i,j:longint;t:re;
begin
for i:=1 to n-1 do
for j:=i to n do
if d[i].y>d[j].y then
begin t:=d[i];d[i]:=d[j];d[j]:=t;end;
end;
procedure discretize;
var top:longint;
begin
sorty;
top:=0;
d[0].x:=-1;d[0].y:=-1;
for i:=1 to n do
begin
if d[i].y<>d[i-1].y then
top:=top+1;
h[top]:=d[i].y;
d[i].fy:=top;
end;
hm:=top;
sortx;
top:=0;
for i:=1 to n do
begin
if d[i].x<>d[i-1].x then
top:=top+1;
l[top]:=d[i].x;
d[i].fx:=top;
end;
lm:=top;
fillchar(map,sizeof(map),0);
fillchar(s,sizeof(s),0);
for i:=1 to n do with d[i] do
map[fx,fy]:=true;
for i:=1 to lm do
for j:=1 to hm do
begin
s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1];
if map[i,j] then inc(s[i,j]);
end;
end;
function dfs(lx,ly,rx,ry,k:longint):longint;
var t1,t2,i,j:longint;
begin
if (lx>rx)or(ly>ry) then exit(max);
if f[lx,ly,rx,ry,k]<max then exit(f[lx,ly,rx,ry,k]);
case k of
1: begin
if (lx=rx)or(ly=ry) then
begin f[lx,ly,rx,ry,k]:=0;exit(0);end;
i:=lx;j:=rx;
while(s[j,ry]-s[j-1,ry]-s[j,ly-1]+s[j-1,ly-1]=0)and(j>lx)do j:=j-1;
while(s[i,ry]-s[i-1,ry]-s[i,ly-1]+s[i-1,ly-1]=0)and(i<rx)do i:=i+1;
if i>j then exit(max);
t1:=ly;t2:=ry;
while(s[j,t1]-s[i-1,t1]-s[j,t1-1]+s[i-1,t1-1]=0)and(t1<ry)do t1:=t1+1;
while(s[j,t2]-s[i-1,t2]-s[j,t2-1]+s[i-1,t2-1]=0)and(t2>ly)do t2:=t2-1;
if t1>t2 then exit(max);
t1:=(l[j]-l[i])*(h[t2]-h[t1]);
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
2: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
3: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,2)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,2)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
4: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,3);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,2)+dfs(i+1,ly,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,3)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,3);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,2)+dfs(lx,i+1,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,3)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
end;
end;
begin
getdata;
discretize;
fillchar(f,sizeof(f),1);
ans:=dfs(1,1,lm,hm,k);
writeln(ans);
end.
状态: Accepted
测评机： Xeond[6]
提交日期： 2011-10-9 15:18:00
有效耗时： 4328毫秒
测试结果1: 通过本测试点|有效耗时844ms
测试结果2: 通过本测试点|有效耗时422ms
测试结果3: 通过本测试点|有效耗时390ms
测试结果4: 通过本测试点|有效耗时391ms
测试结果5: 通过本测试点|有效耗时391ms
测试结果6: 通过本测试点|有效耗时375ms
测试结果7: 通过本测试点|有效耗时375ms
测试结果8: 通过本测试点|有效耗时375ms
测试结果9: 通过本测试点|有效耗时375ms
测试结果10: 通过本测试点|有效耗时390ms
提交代码：
program noip2002t4;
const nn=51;mm=501;max=16843009;
type
re=record
x,y,fx,fy:longint;
end;
var
n,i,hm,lm,j,k,ans,tt:longint;
h,l,y,x:array[0..nn]of longint;
map:array[0..nn,0..nn]of boolean;
s:array[0..nn,0..nn]of longint;
d:array[0..nn]of re;
f:array[0..nn,0..nn,0..nn,0..nn,1..4]of longint;
procedure getdata;
begin
readln(n,k);
for i:=1 to n do with d[i] do readln(x,y);
end;
procedure sortx;
var i,j:longint;t:re;
begin
for i:=1 to n-1 do
for j:=i to n do
if (d[i].x>d[j].x)or((d[i].x=d[j].x)and(d[i].y>d[j].y)) then
begin t:=d[i];d[i]:=d[j];d[j]:=t;end;
end;
procedure sorty;
var i,j:longint;t:re;
begin
for i:=1 to n-1 do
for j:=i to n do
if d[i].y>d[j].y then
begin t:=d[i];d[i]:=d[j];d[j]:=t;end;
end;
procedure discretize;
var top:longint;
begin
sorty;
top:=0;
d[0].x:=-1;d[0].y:=-1;
for i:=1 to n do
begin
if d[i].y<>d[i-1].y then
top:=top+1;
h[top]:=d[i].y;
d[i].fy:=top;
end;
hm:=top;
sortx;
top:=0;
for i:=1 to n do
begin
if d[i].x<>d[i-1].x then
top:=top+1;
l[top]:=d[i].x;
d[i].fx:=top;
end;
lm:=top;
fillchar(map,sizeof(map),0);
fillchar(s,sizeof(s),0);
for i:=1 to n do with d[i] do
map[fx,fy]:=true;
for i:=1 to lm do
for j:=1 to hm do
begin
s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1];
if map[i,j] then inc(s[i,j]);
end;
end;
function dfs(lx,ly,rx,ry,k:longint):longint;
var t1,t2,i,j:longint;
begin
if (lx>rx)or(ly>ry) then exit(max);
if f[lx,ly,rx,ry,k]<max then exit(f[lx,ly,rx,ry,k]);
case k of
1: begin
if (lx=rx)or(ly=ry) then
begin f[lx,ly,rx,ry,k]:=0;exit(0);end;
i:=lx;j:=rx;
while(s[j,ry]-s[j-1,ry]-s[j,ly-1]+s[j-1,ly-1]=0)and(j>lx)do j:=j-1;
while(s[i,ry]-s[i-1,ry]-s[i,ly-1]+s[i-1,ly-1]=0)and(i<rx)do i:=i+1;
if i>j then exit(max);
t1:=ly;t2:=ry;
while(s[j,t1]-s[i-1,t1]-s[j,t1-1]+s[i-1,t1-1]=0)and(t1<ry)do t1:=t1+1;
while(s[j,t2]-s[i-1,t2]-s[j,t2-1]+s[i-1,t2-1]=0)and(t2>ly)do t2:=t2-1;
if t1>t2 then exit(max);
t1:=(l[j]-l[i])*(h[t2]-h[t1]);
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
2: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
3: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,2)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,2)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
4: begin
t1:=mm*mm;
for i:=lx to rx-1 do
begin
t2:=dfs(lx,ly,i,ry,1)+dfs(i+1,ly,rx,ry,3);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,2)+dfs(i+1,ly,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,i,ry,3)+dfs(i+1,ly,rx,ry,1);
if t2<t1 then t1:=t2;
end;
for i:=ly to ry-1 do
begin
t2:=dfs(lx,ly,rx,i,1)+dfs(lx,i+1,rx,ry,3);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,2)+dfs(lx,i+1,rx,ry,2);
if t2<t1 then t1:=t2;
t2:=dfs(lx,ly,rx,i,3)+dfs(lx,i+1,rx,ry,1);
if t2<t1 then t1:=t2;
end;
f[lx,ly,rx,ry,k]:=t1;
exit(t1);
end;
end;
end;
begin
getdata;
discretize;
fillchar(f,sizeof(f),1);
tt:=0;
ans:=dfs(1,1,lm,hm,k);
writeln(ans);
end.