PROG-1036: Equipped

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
const int maxN = 1e4;
const int maxK = 8;
int cost[maxN + 10], bit[maxN + 10];
int dp[maxN + 10][(1 << maxK) + 10];
int N, K, Bit;

int f(int i, int b){
    if((b & Bit) == Bit) return 0;
    if(i == N) return inf;
    if(dp[i][b] != inf) return dp[i][b];
    int x = cost[i + 1] + f(i + 1, (b | bit[i + 1]));
    int y = f(i + 1, b);
    return dp[i][b] = min(x, y);
}

int main(){

    scanf("%d %d", &N, &K);

    Bit = (1 << K) - 1;

    for(int i=1;i<=N;i++){
        scanf("%d", &cost[i]);
        for(int k=K-1;k>=0;k--){
            int b; scanf("%d", &b);
            bit[i] = bit[i] | (b << k);
        }
    }

    for(int b=Bit-1;b>=0;b--)
        dp[N][b] = inf;
    dp[N][Bit] = 0;

    for(int i=N-1;i>=0;i--){
        for(int b=Bit;b>=0;b--){
            dp[i][b] = min( cost[i + 1] + dp[i + 1][b | bit[i + 1]] , dp[i + 1][b] );
        }
    }

    printf("%d", dp[0][0]);

    return 0;
}