Submission #985547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
985547	2024-05-18T07:21:10 Z	alextodoran	Tents (JOI18_tents)	C++17	100 / 100	85 ms	35676 KB

tents

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 3000;
const int MOD = (int) 1e9 + 7;

void add (int &x, const int &y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int N, M;
int dp[N_MAX + 2][N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int n = 0; n <= N; n++) {
        dp[n][0] = 1;
    }
    for (int m = 0; m <= M; m++) {
        dp[0][m] = 1;
    }
    for (int n = 1; n <= N; n++) {
        for (int m = 1; m <= M; m++) {
            dp[n][m] = dp[n - 1][m];
            add(dp[n][m], (ll) dp[n - 1][m - 1] * m * 4 % MOD);
            if (m >= 2) {
                add(dp[n][m], dp[n - 1][m - 2] * ((ll) m * (m - 1) / 2 % MOD) % MOD);
            }
            if (n >= 2) {
                add(dp[n][m], (ll) dp[n - 2][m - 1] * m % MOD * (n - 1) % MOD);
            }
        }
    }
    cout << (dp[N][M] - 1 + MOD) % MOD << "\n";

    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	2512 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	2 ms	4444 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	2512 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	2 ms	4444 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	5 ms	29020 KB	Output is correct
15	Correct	54 ms	33620 KB	Output is correct
16	Correct	4 ms	4700 KB	Output is correct
17	Correct	12 ms	8796 KB	Output is correct
18	Correct	15 ms	14940 KB	Output is correct
19	Correct	61 ms	35504 KB	Output is correct
20	Correct	49 ms	29276 KB	Output is correct
21	Correct	33 ms	21080 KB	Output is correct
22	Correct	33 ms	27264 KB	Output is correct
23	Correct	22 ms	35500 KB	Output is correct
24	Correct	80 ms	35676 KB	Output is correct
25	Correct	65 ms	31320 KB	Output is correct
26	Correct	77 ms	35672 KB	Output is correct
27	Correct	85 ms	35508 KB	Output is correct