Submission #1281865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281865		Faisal_Saqib	Tents (JOI18_tents)	C++20	100 / 100	105 ms	70800 KiB

tents

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
const int N=3002,mod=1e9+7;
ll dp[N][N],ndp[N][N];
int main()
{
    ll n,m;
    cin>>n>>m;
    dp[n][m]=1;
    for(int i=n;i>=0;i--)
    {
        for(ll j=m;j>=0;j--)
        {
            ll w0=(i*(i-1))/2;w0%=mod;
            ll w1=(j*(j-1))/2;w1%=mod;
            // place nothing
            if(i>0)
            {
            dp[i-1][j]+=dp[i][j];
            dp[i-1][j]%=mod;
            }

            // place one
            if(i>0 and j>0)
            {
            dp[i-1][j-1]+=(dp[i][j]*4*j)%mod;
            dp[i-1][j-1]%=mod;
            }
            if(i>0 and j>1)
            {
            // place two in row
            dp[i-1][j-2]+=(w1*dp[i][j])%mod;
            dp[i-1][j-2]%=mod;
            }
            if(i>1 and j>0)
            {
            // place two in same column
            dp[i-2][j-1]+=((i-1)*dp[i][j]*j)%mod;
            }

        }
    }
    ll ans=0;
    // for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            ans+=dp[0][j];
            ans%=mod;
        }
    }
    // cout<<dp[0][0]<<endl;
    cout<<(ans+mod-1)%mod<<endl;
}

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