MAUGIAO - The problem for kid
Tác giả: ladpro98
Ngôn ngữ: Pascal
program maugiao;
uses math;
const maxn=20;
maxV=1 shl maxn;
fi='';
var a:array[0..maxn,0..maxn] of longint;
f:array[-1..maxV] of longint;
way:array[0..maxV] of int64;
n,m:longint;
procedure input;
var inp:text;
i,j:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,n);
for i:=1 to n do
begin
for j:=1 to n do read(inp,a[i,j]);
readln(inp);
end;
close(inp);
end;
function getbit(i,j:longint):boolean;
begin
exit((i shr (j-1) and 1)=1);
end;
procedure dp;
var i,j,t,p:longint;
begin
way[0]:=1;
for j:=1 to 1 shl n - 1 do
begin
t:=0;
for i:=1 to n do
if getbit(j,i) then inc(t);
for i:=1 to n do
if getbit(j,i) then
begin
p:=f[j-1 shl (i-1)]+a[t,i];
if f[j]<p then
begin
f[j]:=p;
way[j]:=way[j-1 shl (i-1)];
end
else
if f[j]=p then way[j]:=way[j]+way[j-1 shl (i-1)];
end;
end;
end;
begin
input;
dp;
write(f[1 shl n-1],' ',way[1 shl n -1]);
end.