Submission #60089

#	Time	Username	Problem	Language	Result	Execution time	Memory
60089		Hassoony	Tents (JOI18_tents)	C++17	100 / 100	559 ms	71804 KiB

tents

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MX=3009;
const ll mod=1e9+7;
ll n,m,dp[MX][MX];
ll DP(ll x,ll rem){
    if(x>n)return 0;
    if(rem==0)return 1ll;
    if(rem<0)return 0;
    if(x==n)return (rem!=m)*1ll;
    ll &ret=dp[x][rem];if(ret!=-1)return ret;
    ret=DP(x+1,rem)%mod;
    ret=(ret+(DP(x+1,rem-1)*4*rem)%mod)%mod;
    ret=(ret+(DP(x+1,rem-2)*(rem*(rem-1)/2))%mod)%mod;
    ret=(ret+(DP(x+2,rem-1)*rem*(n-x-1))%mod)%mod;
    return ret;
}
int main(){
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    cout<<DP(0,m)<<endl;
}

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