Cod sursa(job #36949)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 24 martie 2007 12:43:00
Problema Jocul Flip Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.01 kb
type vector=array[1..16] of 0..1;
    int=1..16;
var v:array[1..16,1..16] of -1000000..1000000;
    s:array[1..16] of longint;
    f,g:text;
    ok:boolean;
    n,m,i,j:integer;
    q,max:longint;
    sa,d:int;
    x:vector;
procedure adauga(var x:vector);
    begin
      if x[n]=0 then x[n]:=1
         else
           begin
             j:=n;
             while x[j]=1 do
               begin
                 x[j]:=0; dec(j);
               end;
             x[j]:=1;
           end;
    end;
procedure quick(sa,d:int);
    var ia:integer;
       t:longint;
       a,b:1..16;
    begin       a:=sa;
      b:=d;
      repeat
        while s[a]<s[b] do b:=b-1;
        t:=s[a]; s[a]:=s[b]; s[b]:=t;
            a:=a+1; ia:=1;
            if a<b then
              begin
                while s[a]<s[b] do a:=a+1;
                  t:=s[a]; s[a]:=s[b]; s[b]:=t;
                  b:=b-1; ia:=0;
              end;
      until b<=a;
      if sa<a-ia then quick(sa,a-ia);
      if a-ia+1<d then quick(a-ia+1,d);
    end;

begin

assign(f,'flip.in');
reset(f);
readln(f,n,m);

for i:=1 to n do
    begin
      for j:=1 to m do
         begin
        read(f,v[i,j]);
        {s[j]:=s[j]+a[i,j];}
          end;
      readln(f);
    end;
close(f);
for i:=1 to n do x[i]:=0;
ok:=true;
while ok do
   begin
     adauga(x);
     q:=0; for i:=1 to n do if x[i]=1 then inc(q);
if q=n then ok:=false
   else
      begin
      fillchar(s,sizeof(s),0);
      q:=0;
     for i:=1 to n do
        if x[i]=1 then
          begin            for j:=1 to m do begin s[j]:=s[j]-v[i,j]; q:=q-v[i,j]; end;
          end else if x[i]=0 then for j:=1 to m do begin s[j]:=s[j]+v[i,j]; q:=q+v[i,j]; end;
     quick(1,m);
     i:=1;
     while (s[i]<0)and(i<=m) do
        begin
          q:=q-(2*s[i]);
          inc(i);
        end;
     if q>max then max:=q;
      end;
    end;
assign(g,'flip.out');
rewrite(g);
if (n=1)and(m=1)then writeln(g,v[1,1]) else writeln(g,max);
close(g);
end.