URAL 1167 Bicolored Horses

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int dp[505][505], arr[505];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, k;
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>arr[i];

    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            dp[i][j]=300000;

    //for(int i=1;i<=k;i++) dp[1][i]=0;
    //for(int i=1;i<=n;i++) dp[i][1]=(arr[i]*(i-arr[i]));
    dp[0][0]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
        {
            int w=0, b=0;
            for(int k=i-1;k>=0;k--)
            {
                if(arr[k]) w++;
                else b++;
                if(dp[k][j-1]+w*b < dp[i][j])
                {
                    dp[i][j] = dp[k][j-1]+w*b;
                }
            }
        }
    cout<<dp[n][k]<<"\n";
    return 0;
}