记录编号	115095	评测结果	AAAAAAAAAA
题目名称	[FZYZOJ 1273] 坦克游戏	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	Pascal	运行时间	0.117 s
提交时间	2014-08-13 19:30:33	内存使用	2.77 MiB

  var  max,n,m,t,r:longint;
       map,le:array[0..51,0..51] of longint;
        s,temp:array[0..101] of longint;
        f:array[0..51,0..51,0..250] of longint;
    function min(x,y:longint):longint;
     begin
      if x<y then min:=x else min:=y;
     end;
    procedure sort(l,m:longint);
    var i,j,mid,t:longint;
     begin
       i:=l;j:=m;mid:=temp[(l+m) div 2];
       repeat
        while temp[i]>mid do inc(i);
        while temp[j]<mid do dec(j);
        if i<=j then begin t:=temp[i];temp[i]:=temp[j];temp[j]:=t;inc(i);dec(j);end;
       until i>j;
      if i<m then sort(i,m);
      if j>l then sort(l,j);
     end;
   procedure init;
    var i,j,k:longint;
     begin
       assign(input,'gametk.in');reset(input);
       assign(output,'gametk.out');rewrite(output);
       readln(n,m,r,t);
       for i:=1 to n do
        begin
         for j:=1 to m do read(map[i,j]);
         readln;
        end;
      k:=0;
      fillchar(temp,sizeof(temp),0);
      fillchar(le,sizeof(le),0);
      max:=0;
      for i:=1 to r+1 do
       for j:=1 to r+1 do
        begin
          if map[i,j]<>0 then begin inc(k);
          temp[k]:=map[i,j];  end;
        end;
      sort(1,k);
      s[0]:=0;
      le[1,1]:=k;
      for i:=1 to k do s[i]:=s[i-1]+temp[i];
      if k>t then k:=t;
      for i:=1 to k do begin f[1,1,i]:=s[i];if f[1,1,i]>max then max:=f[1,1,i];end;
     end;
   procedure main;
    var  i,j,k,p,ir,il,jr,jl,long,ans:longint;
     begin
       for i:=1 to n-r do
        for j:=1 to m-r do
         if (i<>1) or (j<>1) then
          begin
            if i>1 then
             begin
               if i+r<=n then ir:=i+r else ir:=n;
               if j+r<=m then jr:=j+r else jr:=m;
               if i-r>=1 then il:=i-r else il:=1;
               if j-r>=1 then jl:=j-r else jl:=1;
               long:=0;
               for k:=1 to jr-jl+1 do if map[ir,k+jl-1]<>0 then
                begin inc(long);temp[long]:=map[ir,k+jl-1];end;
               sort(1,long);
               s[0]:=0;
               fillchar(s,sizeof(s),0);
               for k:=1 to long do s[k]:=s[k-1]+temp[k];
               ans:=min(le[i-1,j]+long,t-(i+j-2));
               if ans>le[i,j] then le[i,j]:=ans;
               for k:=1 to ans do
                begin
                  f[i,j,k]:=0;
                  for p:=0 to min(long,k) do
                   begin
                     if f[i-1,j,k-p]+s[p]>f[i,j,k] then
                      f[i,j,k]:=f[i-1,j,k-p]+s[p];
                   end;
                  if f[i,j,k]>max then max:=f[i,j,k];
                end;
             end;
           if j>1 then
             begin
               if i+r<=n then  ir:=i+r else ir:=n;
               if j+r<=m then jr:=j+r else jr:=m;
               if i-r>=1 then il:=i-r else il:=1;
               if j-r>=1 then jl:=j-r else jl:=1;
               long:=0;
               for k:=1 to ir-il+1 do if map[k+il-1,jr]<>0 then
                begin inc(long);temp[long]:=map[k+il-1,jr];end;
               sort(1,long);
               s[0]:=0;
               fillchar(s,sizeof(s),0);
               for k:=1 to long do s[k]:=s[k-1]+temp[k];
               ans:=min(le[i,j-1]+long,t-(i+j-2));
               if ans>le[i,j] then le[i,j]:=ans;
               for k:=1 to ans do
                begin
                  for p:=0 to min(long,k) do
                  begin
                    if f[i,j-1,k-p]+s[p]>f[i,j,k] then
                     f[i,j,k]:=f[i,j-1,k-p]+s[p];
                  end;
                 if f[i,j,k]>max then
                  begin max:=f[i,j,k];end;
               end;
            end;
         end;
       writeln(max);
       close(input);
       close(output);
    end;
  begin
    init;
    main;
  end.