Cod sursa(job #109586)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 25 noiembrie 2007 11:59:24
Problema Teren Scor 30
Compilator fpc Status done
Runda preONI 2008, Runda 1, Clasa a 9-a Marime 1.72 kb
program teren;
var f,g:text;
        a:array[0..301,0..301] of longint;
        m,n,x:longint;


procedure citire;
var i,j,y:longint;
begin
        assign(f,'teren.in');reset(f);
        assign(g,'teren.out');rewrite(g);
        readln(f,m,n,x);
        fillchar(a,sizeof(a),0);
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                read(f,y);
                                a[i,j]:=y+a[i-1,j]+a[i,j-1]-a[i-1,j-1]
                        end;
        close(f);
end;

function cbin(p,u,col,target,minus,maxl:longint):longint;
var m:longint;
begin
        if p>u then
                cbin:=0 else
        begin
                m:=(p+u) div 2;
                if a[m,col]-a[minus,col]<target then
                        cbin:=cbin(m+1,u,col,target,minus,maxl) else
                        if a[m-1,col]-a[minus,col]<target then
                                cbin:=m else
                                        cbin:=cbin(p,m-1,col,target,minus,maxl);
        end;
end;



procedure prel;
var i,j,max,k,l,ar,arie:longint;
begin
        max:=0;
        for i:=1 to m do
                for j:=1 to n do
                        for k:=0 to j-1 do
                                begin
                                        arie:=a[i,j]-a[i,k];
                                        if x>=arie then l:=0 else
                                                l:=cbin(1,i,j,arie-x,k,i);
                                        ar:=(j-k)*(i-l);
                                        if ar>max then max:=ar;
                                end;
        writeln(g,max);
        close(g);
end;


begin
        citire;
        prel;
end.