답안 #887952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887952	2023-12-15T15:25:07 Z	boris_mihov	Tents (JOI18_tents)	C++17	100 / 100	181 ms	78932 KB

tents

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 3000 + 10;
const int MOD = 1e9 + 7;

llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];

llong rec(int n, int m)
{
    if (n < 0 || m < 0)
    {
        return 0;
    }

    if (n == 0 || m == 0)
    {
        return 1;
    }

    if (bl[n][m])
    {
        return dp[n][m];
    }

    bl[n][m] = true;
    dp[n][m] = rec(n - 1, m);
    dp[n][m] += 4 * rec(n - 1, m - 1) * m;
    dp[n][m] += rec(n - 1, m - 2) * m * (m - 1) / 2;
    dp[n][m] += rec(n - 2, m - 1) * m * (n - 1);
    dp[n][m] %= MOD;
    return dp[n][m];
}

int n, m;
int main()
{
    std::cin >> n >> m;
    std::cout << rec(n, m) - 1 << '\n';
    return 0;

}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	7004 KB	Output is correct
5	Correct	1 ms	2652 KB	Output is correct
6	Correct	1 ms	7260 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	3 ms	9308 KB	Output is correct
9	Correct	1 ms	4908 KB	Output is correct
10	Correct	2 ms	9308 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	3 ms	9308 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	7004 KB	Output is correct
5	Correct	1 ms	2652 KB	Output is correct
6	Correct	1 ms	7260 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	3 ms	9308 KB	Output is correct
9	Correct	1 ms	4908 KB	Output is correct
10	Correct	2 ms	9308 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	3 ms	9308 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	9 ms	62556 KB	Output is correct
15	Correct	114 ms	74368 KB	Output is correct
16	Correct	2 ms	7260 KB	Output is correct
17	Correct	16 ms	20988 KB	Output is correct
18	Correct	28 ms	32648 KB	Output is correct
19	Correct	133 ms	78168 KB	Output is correct
20	Correct	115 ms	67524 KB	Output is correct
21	Correct	63 ms	46428 KB	Output is correct
22	Correct	69 ms	60296 KB	Output is correct
23	Correct	45 ms	77904 KB	Output is correct
24	Correct	181 ms	78932 KB	Output is correct
25	Correct	138 ms	69712 KB	Output is correct
26	Correct	153 ms	76652 KB	Output is correct
27	Correct	177 ms	78484 KB	Output is correct