Submission #478329

#	Time	Username	Problem	Language	Result	Execution time	Memory
478329		Mike4235	Tents (JOI18_tents)	C++17	100 / 100	217 ms	70852 KiB

tents

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

void add(int& a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int mul(int a, int b) {
    return a * b % MOD;
}

int n, m;
int dp[3005][3005];

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> m;

    for1(i,0,n) dp[i][0] = 1;
    for1(j,0,m) dp[0][j] = 1;

    for1(i,1,n) {
        for1(j,1,m) {
            if (i > 1) add(dp[i][j], mul(dp[i - 2][j - 1], j * (i - 1)));
            if (j > 1) add(dp[i][j], mul(dp[i - 1][j - 2], j * (j - 1) / 2));
            add(dp[i][j], dp[i - 1][j]);
            add(dp[i][j], mul(dp[i - 1][j - 1], 4 * j));
        }
    }

    cout << (dp[n][m] - 1 + MOD) % MOD;
    
}

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