Submission #1077668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077668		nikolamanolov	Tents (JOI18_tents)	C++14	100 / 100	212 ms	67664 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long dp[3004][3004];
bool iz[3004][3004];
long long rec(long long i, long long j)
{
    if (i<0 || j<0) return 0;
    if (i==0 || j==0) return 1;

    if (iz[i][j]) return dp[i][j];

    long long ans=0;
    ans=(ans+rec(i-1, j))%MOD;
    ans=(ans+rec(i-1, j-1)*4*j)%MOD;
    ans=(ans+rec(i-1, j-2)*(j*(j-1)/2))%MOD;
    ans=(ans+rec(i-2, j-1)*j*(i-1))%MOD;
    iz[i][j]=true;
    return dp[i][j]=ans;
}

long long n, m;

int main ()
{
    cin>>n>>m;
    cout<<rec(n, m)-1<<endl;
}

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