Submission #45862

#	Time	Username	Problem	Language	Result	Execution time	Memory
45862		khohko	Tents (JOI18_tents)	C++17	100 / 100	292 ms	82812 KiB

tents

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define lol long long
#define pb push_back
//#define mp make_pair
#define fr first
#define sc second
#define MAX ((lol)(1e9+100))
#define MX ((lol)(4e9+100))
#define ARRS ((lol)(5e5+100))
#define MOD ((lol)(1e9+7))
#define EP ((double)(1e-9))
#define EPS ((double)(1e-8))
#define pb push_back
#define PI ((double)3.141592653)
#define LG 21

ll dp[4000][4000];


ll go(ll n,ll m){
    if(n<0||m<0)return 0;
    if(n==0||m==0)return 1;
    if(dp[n][m]>=0)return dp[n][m];
   // cout<<m*(m-1)/2<<endl;
    //        10              1*1
    dp[n][m]=go(n-1,m)+m*(m-1)/2*go(n-1,m-2)+m*(n-1)*go(n-2,m-1)+m*4*go(n-1,m-1);
   // cout<<n<<" "<<m<<" "<<dp[n][m]<<endl;
    dp[n][m]%=MOD;
    return dp[n][m];
}


int main(){
    #ifdef KHOKHO
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif // KHOKHO
    ios::sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            dp[i][j]=-1;
        }
    }
    cout<<go(n,m)-1;

}

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