Submission #246637

#	Time	Username	Problem	Language	Result	Execution time	Memory
246637		fivefourthreeone	Tents (JOI18_tents)	C++17	100 / 100	109 ms	70776 KiB

tents

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 3001;
ll dp[mxN][mxN];
int n, m;
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    owo(i, 0, n+1) {
        owo(j, 0, m+1) {
            if(i==0||j==0) dp[i][j]=1;
            else {
                dp[i][j] = dp[i-1][j];
                dp[i][j] = (dp[i][j]+4LL*dp[i-1][j-1]*j)%MOD;
                if(j>1) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-2]*1LL*j*(j-1)/2)%MOD;
                }
                if(i>1) {
                    dp[i][j] = (dp[i][j] + dp[i-2][j-1]*1LL*j*(i-1))%MOD;
                }
            }
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        }
    }
    cout<<(dp[n][m]-1)<<"\n";
    return 0;
}

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