I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
less than 100K memory ! why ? How can they do it ? can anybody tell
me ?

> I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
> less than 100K memory ! why ? How can they do it ? can anybody tell
> me ?

how?
i managed a 0.09 O(n^3) but how do u do n^2??
i might have an N^2 ideea but it n^2 memory......

X[i]: how many black horses are in the first i horses
Y[i]: how many white horses are in the first i horses

We use Dp.
F[i,j] = min { F[i-1,k] + (X[j]-X[k])*(Y[j]-Y[k]) } | K<J

The answer is F[K,N].

Suppose F[i,j] get the minimal value when k=k0.
Let W[i,j]=k0.

You can prove : w[i,j-1]<=w[i,j]<=w[i+1,j]

So you can solve this problem in o(n^2).

Sorry, could you explain please what's k0?