Submission #342713

#	Time	Username	Problem	Language	Result	Execution time	Memory
342713		bigDuck	Tents (JOI18_tents)	C++14	100 / 100	462 ms	71060 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, a[300010], q, l, r;

int dp[3010][3010];
int mod=((int)1e9)+7;


int32_t main(){
INIT
cin>>n>>m;
dp[0][0]=1;
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        if(j>=2){
            dp[i][j]=(dp[i][j]+((max(dp[i-1][j-2], 1ll)*(j*(j-1)/2))%mod)%mod)%mod;
        }
        dp[i][j]=(dp[i][j]+(max(dp[i-1][j-1], 1ll)*4*(j))%mod)%mod;
        if(i>=2){
            dp[i][j]=(dp[i][j]+(max(dp[i-2][j-1], 1ll)*(j)*(i-1) )%mod)%mod;
        }
        dp[i][j]=(dp[i][j]+max(dp[i-1][j], 1ll) ) %mod;
        //cout<<dp[i][j]<<" ";
    }
    //cout<<"\n";
}
cout<<(dp[n][m]-1);

return 0;
}

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