const
  maxn=500;
var
  n,k:integer;
  s:array[1..maxn]of byte;
  f:array[1..maxn,1..maxn]of integer;
procedure init;
var i,j:integer;
begin
{  assign(input,'in.in');reset(input);}
  readln(n,k);
  for i:=1 to n do readln(s[i]);
end;

function g(p1,p2:integer):integer;
var i,sum:integer;
begin
  sum:=0;
  for i:=p1 to p2 do if s[i]=1 then inc(sum);
  g:=(p2-p1+1-sum)*sum;
end;

procedure dp;
var i,j,mik,i2,t:integer;
begin
  for i:=1 to n do
    begin
      if i<k then mik:=i else mik:=k;
      for j:=1 to mik do
        begin
          f[i,j]:=maxint;
          if j=1 then f[i,j]:=g(1,i)
          else
            for i2:=1 to i-j+1 do
              begin
                t:=f[i-i2,j-1]+g(i-i2+1,i);
                if t<f[i,j] then f[i,j]:=t;
              end;
        end;
    end;
end;

{=============main==============}
begin
init;
dp;
writeln(f[n,k]);
end.

How to solve it in O(n) time?

How to slove it in (n^2). plz