QBSELECT - VOI06 Chọn ô

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10000;
  oo=1000000000;
var
  n:longint;
  a:array[1..MAXN,1..4] of longint;
  d:array[0..MAXN,0..15] of longint;
procedure inp;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do read(f,a[i,1]);
  for i:=1 to n do read(f,a[i,2]);
  for i:=1 to n do read(f,a[i,3]);
  for i:=1 to n do read(f,a[i,4]);
  close(f);
end;
procedure ans;
var
  f:text;
  mask,kq:longint;
begin
  assign(f,FOUT); rewrite(f);
  kq:=-oo;
  for mask:=0 to 15 do
    kq:=max(kq,d[n,mask]);
  writeln(f,kq);
  close(f);
end;
procedure refine;
var
  i,j,kq:longint;
  f:text;
begin
  for i:=1 to n do
  for j:=1 to 4 do
    if a[i,j]>0 then exit;
  kq:=-oo;
  assign(f,FOUT); rewrite(f);
  for i:=1 to n do
  for j:=1 to 4 do
    kq:=max(kq,a[i,j]);
  writeln(f,kq);
  close(f);
  halt;
end;
procedure solve;
var
  mask,mask2,i,j,sum:longint;
begin
  for i:=1 to n do
  for mask:=0 to 15 do
  if (mask and (mask shl 1)=0) and (mask and (mask shr 1)=0) then
    begin
      sum:=0;
      for j:=0 to 3 do
        if (mask shr j) and 1=1 then sum:=sum+a[i,j+1];
      for mask2:=0 to 15 do
      if (mask2 and (mask2 shl 1)=0) and (mask2 and (mask2 shr 10)=0) then
        if mask and mask2=0 then
          d[i,mask]:=max(d[i,mask],d[i-1,mask2]+sum);
    end;
end;
begin
  inp;
  refine;
  solve;
  ans;
end.

Download