Submission

Score: 100

User: KantaponZ

Problemset: กองไฟ

Language: cpp

Time: 0.036 second

Submitted On: 2026-01-22 00:00:09

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

#define ll long long
int N, max_a, max_b, max_c;
ll dp[155][4][4][55][55];
ll MOD = 1e9 + 7;
vector<int> v;

ll solve(int idx, int first, int cur, int a, int b) {
    int c = idx - a - b;
   
    if (idx == N) {
        if (cur == first) return 0LL;

        return 1LL;
    }
    if (dp[idx][first][cur][a][b] != -1) {
        //cout << idx << " " << cur << " " << a << " " << b <<"\n";
        return dp[idx][first][cur][a][b];
    }
    

    if (idx == 1) {
        v.push_back(first);
    }

    ll ans = 0;
    for (int i = 1; i <= 3; i++) {
        if (cur == i) continue;
        if (i == 1) {
            if (a + 1 > max_a) continue;
            v.push_back(i);
            ans = (ans + solve(idx + 1, first, i, a + 1, b)) % MOD;
            v.pop_back();
        } else if (i == 2) {
            if (b + 1 > max_b) continue;
            //v.push_back(i);
            ans = (ans + solve(idx + 1, first, i, a, b + 1)) % MOD;
            //v.pop_back();
        } else {
            if (c + 1 > max_c) continue;
            //v.push_back(i);
            ans = (ans + solve(idx + 1, first, i, a, b)) % MOD;
            //v.pop_back();
        }
    }

    if (idx == 1) {
        //v.pop_back();
    }

    dp[idx][first][cur][a][b] = ans;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> max_a >> max_b >> max_c;
    //cout << N << max_a << max_b << max_c << "\n";
    memset(dp, -1, sizeof dp);
    ll ans = 0;

    //cout << solve(1, 1, 1, 1, 0);

    for (int i = 1; i <= 3; i++) {
        //ans = (ans + solve(1, i, i, 0, 0)) % MOD;
        if (i == 1 && max_a != 0) ans = (ans + solve(1, i, i, 1, 0)) % MOD;
        if (i == 2 && max_b != 0) ans = (ans + solve(1, i, i, 0, 1)) % MOD;
        if (i == 3 && max_c != 0) ans = (ans + solve(1, i, i, 0, 0)) % MOD;
    }
    cout << ans;
}