p310.ans1
======================
144

=================
p310.ans2
======================
26

=================
p310.ans3
======================
1

=================
p310.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k;

void read() { cin >> n >> m >> k; }

void solve() {
    // Iron boards are 1 bits. The constraint is that every window of m
    // consecutive boards holds at least k iron boards, which only constrains
    // complete windows; there are n - m + 1 of them.
    //
    // dp[i][mask] = number of ways to fill the first m + i boards such that the
    // i-th window (boards i..i+m-1) equals mask and all windows up to it are
    // valid. The base layer dp[0][mask] enumerates the first window directly,
    // keeping only masks with popcount >= k. To extend, we slide the window by
    // one board: appending bit b turns mask into ((mask << 1) | b) truncated to
    // m bits, again required to have popcount >= k. The answer sums the final
    // layer over all masks.

    vector<vector<int64_t>> dp(n - m + 1, vector<int64_t>(1 << m, 0));

    for(int mask = 0; mask < (1 << m); mask++) {
        int cnt = __builtin_popcount(mask);
        if(cnt < k) {
            continue;
        }

        dp[0][mask] = 1;
    }

    for(int i = 1; i < n - m + 1; i++) {
        for(int mask = 0; mask < (1 << m); mask++) {
            if(dp[i - 1][mask] == 0) {
                continue;
            }

            for(int bit = 0; bit < 2; bit++) {
                int new_mask = (mask << 1) | bit;
                new_mask &= (1 << m) - 1;

                int cnt = __builtin_popcount(new_mask);
                if(cnt < k) {
                    continue;
                }

                dp[i][new_mask] += dp[i - 1][mask];
            }
        }
    }

    int64_t ans = 0;
    for(int mask = 0; mask < (1 << m); mask++) {
        ans += dp[n - m][mask];
    }

    cout << ans << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p310.in1
======================
10 2 1

=================
p310.in2
======================
5 5 2

=================
p310.in3
======================
3 2 2

=================
statement.txt
======================
310. Hippopotamus
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



After fixing your roof, you still think that it looks unpretty. So you opt for a new one, consisting of n consecutive long narrow boards. You have two types of boards: wooden ones and iron ones, giving you an amazing total of 2n possible roofs.

But the safety should not be left aside. Having considered the weight and the cruising speed of a falling hippopotamus, you decide to have at least k iron boards among every m consecutive boards.

How many possibilities do you have?

Input
The input file contains three integers, n, m and k, separated by spaces and/or line breaks. 1 ≤ n ≤ 60, 1 ≤ m ≤ 15, 0 ≤ k ≤ m ≤ n.

Output
Output the number of possibilities.

Example(s)
sample input
sample output
10 2 1
144

sample input
sample output
5 5 2
26

sample input
sample output
3 2 2
1

=================
