Competitive Programming Solutions

abc185_c - Duodecim Ferra

13 Dec 2020 — Tags: combinatorics,dp — URL

Compute the number of ways to cut a log of width $l$, $C(l - 1, 11)$.

Time complexity: $O(l^2)$

Memory complexity: $O(l^2)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int l;
    cin >> l;
    vector<vector<ll>> C(l + 1, vector<ll>(l + 1, 0));
    C[0][0] = 1;
    for (int n = 1; n <= l; ++n)
    {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k)
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }
    cout << C[l - 1][11] << endl;
    return 0;
}

Related posts