coin combinations 1 cses code example

Example: coin combinations 1 cses solution

#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;#define pb push_back#define rsz resize#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()using pi = pair<int,int>;#define f first#define s second#define mp make_pairvoid setIO(string name = "") { // name is nonempty for USACO file I/O    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output    if(sz(name)){        freopen((name+".in").c_str(), "r", stdin); // see Input & Output        freopen((name+".out").c_str(), "w", stdout);    }}
ll dp[1000001];
const int MOD = (int) 1e9 + 7;
int main(){    int n, x; cin >> n >> x;    vi coins(n);    for (int i = 0; i < n; i++) {        cin >> coins[i];    }    dp[0] = 1;    for (int weight = 0; weight <= x; weight++) {        for (int i = 1; i <= n; i++) {            if(weight - coins[i - 1] >= 0) {                dp[weight] += dp[weight - coins[i - 1]];                dp[weight] %= MOD;            }        }    }    cout << dp[x] << '\n';}

Tags:

Misc Example