记录编号	30456	评测结果	AAAAAAAAAA
题目名称	技能树	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.083 s
提交时间	2011-10-29 12:34:45	内存使用	5.12 MiB

program skill;
var
  f:array[0..50,0..50,0..500]of longint;
  n,m,i,j,h,l,ans,th,k,max,jilu:longint;
  a,sum,cost:array[0..50,0..50]of longint;
begin
  assign (input,'skill.in');
  reset (input);
  assign (output,'skill.out');
  rewrite (output);
    readln (n,m);
    for i:=1 to n do
    begin
      for j:=1 to n-i+1 do
        read (a[i,j]);
      readln
    end;
    for i:=1 to n do
      for j:=1 to n-i+1 do
      begin
        sum[i,j]:=a[i,j];
        cost[i,j]:=1;
        th:=j;
        k:=i;
        k:=k-2;
        while k>0 do
        begin
          inc(cost[i,j]);
          inc(th);
          sum[i,j]:=sum[i,j]+a[k,th];
          k:=k-2
        end
      end;
    for i:=1 to n do
      for j:=1 to n do
        for k:=1 to m do
          f[i,j,k]:=maxlongint;
    for l:=1 to n do
      for h:=1 to n-l+1 do
      begin
        if h=1 then
        begin
          max:=0;
          for k:=1 to m do
          begin
            if (h+1<=n)and(l-1>0)and(f[l-1,h+1,k-cost[h,l]]<>maxlongint)
            and(f[l-1,h+1,k-cost[h,l]]+sum[h,l]>max) then
              max:=f[l-1,h+1,k-cost[h,l]]+sum[h,l];
            for i:=0 to l-1 do
              if (f[i,1,k-1]<>maxlongint)and(f[i,1,k-1]+a[1,l]>max) then
                max:=f[i,1,k-1]+a[1,l];
            if max<>0 then
              f[l,1,k]:=max
          end
        end
        else
        for k:=1 to m do
        begin
            max:=0;
            if (k-cost[h,l]>0) then
            begin
              if (f[l,h-1,k-cost[h,l]]<>maxlongint)
              and(f[l,h-1,k-cost[h,l]]+sum[h,l]>max) then
                max:=f[l,h-1,k-cost[h,l]]+sum[h,l];
              if (h+1<=n)and(l-1>0)and(f[l-1,h+1,k-cost[h,l]]<>maxlongint)
              and(f[l-1,h+1,k-cost[h,l]]+sum[h,l]>max) then
                max:=f[l-1,h+1,k-cost[h,l]]+sum[h,l]
            end;
            if max<>0 then
              f[l,h,k]:=max
        end
      end;
      for i:=1 to n do
        if (f[i,1,m]<>maxlongint)and(f[i,1,m]>ans) then
        begin
          ans:=f[i,1,m];
          jilu:=i
        end;
      writeln (ans);
  close (input);
  close (output)
end.