oj.uz

Submission #987223

# Submission time Handle Problem Language Result Execution time Memory
987223 2024-05-22T11:05:58 Z steveonalex Tents (JOI18_tents) C++17
100 / 100
 131 ms 38804 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)

// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(T &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int MOD = 1e9 + 7;
const int N = 4000;
int dp[N][N];

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

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    dp[n][m]= 1;

    for(int i = n; i>=0; --i) for(int j = m; j>=0; --j) if (dp[i][j]){
        if (i >= 1) add(dp[i-1][j], dp[i][j]);
        if (i >= 1 && j >= 1) add(dp[i-1][j-1], 1LL * dp[i][j] * 4 * j);
        if (i >= 2 && j >= 1){
            add(dp[i-2][j-1], 1LL * dp[i][j] * (i-1) * j);
        }
        if (j >= 2 && i >= 1){
            add(dp[i-1][j-2], 1LL * dp[i][j] * j * (j-1) / 2);
        }
    }
    

    int ans = 0;
    for(int j = 0; j < m; ++j) add(ans, dp[0][j]);
    cout << ans << "\n";


    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 1880 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 1880 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 5 ms 9560 KB Output is correct
15 Correct 83 ms 29324 KB Output is correct
16 Correct 2 ms 1372 KB Output is correct
17 Correct 11 ms 4956 KB Output is correct
18 Correct 21 ms 9308 KB Output is correct
19 Correct 95 ms 32592 KB Output is correct
20 Correct 75 ms 26192 KB Output is correct
21 Correct 44 ms 16208 KB Output is correct
22 Correct 55 ms 19784 KB Output is correct
23 Correct 39 ms 19536 KB Output is correct
24 Correct 131 ms 38804 KB Output is correct
25 Correct 92 ms 30180 KB Output is correct
26 Correct 106 ms 34472 KB Output is correct
27 Correct 118 ms 37460 KB Output is correct