Submission #1351000

#TimeUsernameProblemLanguageResultExecution timeMemory
1351000rahidilbayramliTents (JOI18_tents)C++20
100 / 100
73 ms71064 KiB
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pb push_back
#define sz(v) (ll)(v.size())
#define f first
#define s second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
const ll mod = 1e9+7;
void solve()
{
    ll h, w, i, j;
    cin >> h >> w;
    ll dp[h+5][w+5];
    for(i = 0; i <= h + 1; i++)
    {
        for(j = 0; j <= w + 1; j++)
        {
            dp[i][j] = 0;
            if(!i || !j)
                dp[i][j] = 1;
        }
    }
    for(i = 1; i <= h; i++)
    {
        for(j = 1; j <= w; j++)
        {
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= mod;
            dp[i][j] += dp[i-1][j-1] * 4 * j;
            dp[i][j] %= mod;
            if(j >= 2){
                dp[i][j] += dp[i-1][j-2] * ((j * (j - 1)) / 2);
                dp[i][j] %= mod;
            }
            if(i > 1){
                dp[i][j] += dp[i-2][j-1] * j * (i - 1);
                dp[i][j] %= mod;
            }
        }
    }
    dp[h][w]--;
    if(dp[h][w] < 0)
        dp[h][w] += mod;
    dp[h][w] %= mod;
    cout << dp[h][w] << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...