# <a href="https://codeforces.com/problemset/problem/543/A">Contest #2 - C. Writing Code</a>

- Intinya soal ini, kita disuruh mencari banyaknya cara berbeda untuk menulis $m$ baris kode dengan syarat banyaknya bugs $\le b$.
- Sangat jelas bahwa soal ini dapat diselesaikan menggunakan DP.
- Terdapat 2 states dalam DP ini: <br> 1. Banyak baris kode <br> 2. Banyak bugs
- $dp[i][j]$ didefinisikan sebagai banyaknya cara berbeda untuk menulis $i$ baris kode dengan terdapat $j$ bugs di dalamnya.
- Base case: $dp[0][0] = 1$
- Alasan didapatkannya base case tersebut karena satu-satunya kemungkinan banyak bugs dalam $0$ baris kode adalah $0$.
- Perlu diperhatikan bahwa perbedaan urutan programmers tidak mempengaruhi konfigurasi, contoh: $\{a[1], a[2]\} = \{a[2], a[1]\}$, sehingga outer loop-nya adalah iterasi programmer agar menghindari perbedaan dalam konteks permutasi.
- Urutan hierarki nested loop: <br> 1. Programmer $\{i |1 \le i \le n\}$ <br> 2. Banyak baris kode $\{j | 1 \le j \le m\}$ <br> 3. Banyak bugs $\{k|0 \le k \le b\}$
- Kompleksitas waktu: $O(n \cdot m \cdot (b + 1))$

:::spoiler Solusi

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

int n, m, b, mod, a[505], dp[505][505];

// dp[i][j] = banyaknya cara agar di dalam i lines, terdapat j bugs

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

  cin >> n >> m >> b >> mod;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }

  dp[0][0] = 1;

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      for (int k = 0; k <= b; ++k) {
        if (a[i] <= k) {
          dp[j][k] += dp[j - 1][k - a[i]];
          dp[j][k] %= mod;
        }
      }
    }
  }
  
  int ans = 0;
  for (int j = 0; j <= b; ++j) {
    ans += dp[m][j];
    ans %= mod;
  }
  cout << ans << '\n';

}

:::