Editing 2015 Jan Gold Problem 2 Moovie Mooving (section)

== Code ==
=== C++ ===

<pre>
#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 22;
const int MAXC = 1010;

int N, L;
int D[MAXN];
std::vector<int> S[MAXN];
int C[MAXN];
int dp[1 << MAXN];

int popcount(int x) {
    return __builtin_popcount(x);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        std::cin >> D[i] >> C[i];
        S[i].resize(C[i]);
        for (int j = 0; j < C[i]; ++j) {
            std::cin >> S[i][j];
        }
    }

    std::fill(dp + 1, dp + (1 << N), -1);

    int ans = -1;
    for (int msk = 0; msk < (1 << N); ++msk) {
        int cur = dp[msk];
        if (cur == -1) continue;

        if (cur >= L) {
            int cnt = popcount(msk);
            if (ans == -1 || cnt < ans) ans = cnt;
        }

        for (int i = 0; i < N; ++i) {
            if (msk & (1 << i)) continue;

            int nmsk = msk | (1 << i);
            auto idx = std::upper_bound(S[i].begin(), S[i].end(), cur) - 1;
            if (idx == S[i].begin() - 1) continue;

            int t = *idx + D[i];
            if (t > dp[nmsk]) dp[nmsk] = t;
        }
    }

    std::cout << ans << '\n';
    return 0;
}

</pre>


=== Java ===

<pre>
import java.util.*;
import java.io.*;

public class Main {
    static final int MAXN = 22;
    static final int MAXC = 1010;

    static int N, L;
    static int[] D = new int[MAXN];
    static ArrayList<Integer>[] S = new ArrayList[MAXN];
    static int[] C = new int[MAXN];
    static int[] dp = new int[1 << MAXN];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        L = in.nextInt();
        for (int i = 0; i < N; ++i) {
            D[i] = in.nextInt();
            C[i] = in.nextInt();
            S[i] = new ArrayList<>();
            for (int j = 0; j < C[i]; ++j) {
                S[i].add(in.nextInt());
            }
        }

        Arrays.fill(dp, 1, 1 << N, -1);

        int ans = -1;
        for (int msk = 0; msk < (1 << N); ++msk) {
            int cur = dp[msk];
            if (cur == -1) continue;

            if (cur >= L) {
                int cnt = Integer.bitCount(msk);
                if (ans == -1 || cnt < ans) ans = cnt;
            }

            for (int i = 0; i < N; ++i) {
                if ((msk & (1 << i)) != 0) continue;

                int nmsk = msk | (1 << i);
                int idx = Collections.binarySearch(S[i], cur);
                if (idx < 0) idx = -idx - 2;
                if (idx == -1) continue;

                int t = S[i].get(idx) + D[i];
                if (t > dp[nmsk]) dp[nmsk] = t;
            }
        }

        System.out.println(ans);
    }
}
</pre>

=== Python ===

<pre>
import sys
from bisect import bisect_right

MAXN = 22
MAXC = 1010

def popcount(x):
    return bin(x).count('1')

def main():
    N, L = map(int, input().split())
    D = [0] * MAXN
    S = [[] for _ in range(MAXN)]
    C = [0] * MAXN
    dp = [-1] * (1 << MAXN)

    for i in range(N):
        D[i], C[i], *showtimes = map(int, input().split())
        S[i] = showtimes

    dp[0] = 0

    ans = -1
    for msk in range(1 << N):
        cur = dp[msk]
        if cur == -1:
            continue

        if cur >= L:
            cnt = popcount(msk)
            if ans == -1 or cnt < ans:
                ans = cnt

        for i in range(N):
            if msk & (1 << i):
                continue

            nmsk = msk | (1 << i)
            idx = bisect_right(S[i], cur) - 1
            if idx == -1:
                continue

            t = S[i][idx] + D[i]
            if t > dp[nmsk]:
                dp[nmsk] = t

    print(ans)

if __name__ == "__main__":
    main()
</pre>

[[Category:Yearly_2014_2015]]
[[Category:Gold]]
[[Category:Graph]]
[[Category:2D Array]]
[[Category:Dynamic Programming]]
[[Category:Bitmask]]