i got AC with an O(N^3) but when i changed it to O(N^2) i got WA and
donna know why, i get WA in higher Test case but all of my variable
is good enough and i get AC with O(N^3) with them, anyway please
help me ,here is my O(N^2) one :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~``
{1029}
var
  a,c         : array[0..100,0..500] of longint;
  ans         : array[0..100,0..500] of integer;
  answer      : array[0..50000] of integer;
  b           : array[0..600] of int64;
  n,i,j,m,z   : longint;
  k,p         : longint;
begin
  readln(m,n);p:=0;
  fillchar(a,sizeof(a),0);
  fillchar(answer,sizeof(answer),0);
  fillchar(b,sizeof(b),0);
  for i:=1 to m do
  begin
    b[0]:=0;
    k:=maxlongint;z:=1;
    for j:=1 to n do
    begin
      read(a[i,j]);
      b[j]:=a[i,j]+b[j-1];
      c[i,j]:=c[i-1,j]+a[i,j];ans[i,j]:=j;
      if (b[j]-b[z-1]+c[i-1,z]<c[i,j]) then
          begin
            c[i,j]:=b[j]-b[z-1]+c[i-1,z];
            ans[i,j]:=z;
          end;
      if c[i,j]<k then
        begin
          k:=c[i,j];
          z:=j;
        end;
    end;
  end;
  for i:=1 to m do
  begin
    b[n+1]:=0;k:=maxlongint;z:=n;
    for j:=n  downto 1 do
      begin
        b[j]:=a[i,j]+b[j+1];
        if (b[j]-b[z+1]+c[i-1,z]<c[i,j]) then
          begin
            c[i,j]:=b[j]-b[z+1]+c[i-1,z];
            ans[i,j]:=z;
          end;
        if c[i,j]<k then
          begin
            k:=c[i,j];
            z:=j;
          end;
      end;
  end;
  k:=c[m,1];j:=1;i:=m;
  for z:=2 to n do
    if c[m,z]<k then
      begin
        j:=z;
        k:=c[m,z];
      end;
  while (i>0) do
    begin
      if ans[i,j]=j then
      begin
      dec(i);
      inc(p);
      answer[p]:=j;
      end
      else
        begin
          if ans[i,j]>j then
            begin
              for z:=j to ans[i,j] do
                begin
                  inc(p);
                  answer[p]:=z;
                end;
            end
          else
            begin
              for z:=j downto ans[i,j] do
                begin
                  inc(p);
                  answer[p]:=z;
                end;
            end;
          j:=ans[i,j];
          dec(i);
        end;
    end;
  for i:=p downto 1 do
    writeln(answer[i]);
end.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
thanx
SABER
ssf_digi@hotmail.com