Submission #1173034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173034		VMaksimoski008	Tents (JOI18_tents)	C++20	48 / 100	330 ms	222536 KiB

tents

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

int n, m;
ll dp[305][305][305];

ll coef(ll x) {
    x = x * (x - 1) / 2;
    return x % mod;
}

ll f(int r, int c, int k) {
    if(r == n + 1) return 1;
    if(dp[r][c][k] != -1) return dp[r][c][k];

    //nisto
    ll ans = f(r+1, c, k);

    //EW
    if(c >= 2) ans = (ans + f(r+1, c-2, k) * coef(c)) % mod;
    
    //N na S
    if(k) ans = (ans + f(r+1, c, k-1) * k) % mod;

    //S sto ne e na N
    if(c >= 1) ans = (ans + f(r+1, c-1, k) * c) % mod;

    //N
    if(c >= 1) ans = (ans + f(r+1, c-1, k+1) * c) % mod;

    if(c >= 1) ans = (ans + f(r+1, c-1, k) * 2ll * c) % mod;

    return dp[r][c][k] = ans;
}

signed main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    cout << (f(1, m, 0) - 1 + mod) % mod << '\n';
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52