Submission #797870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797870	2023-07-30T04:21:56 Z	vjudge1	Tents (JOI18_tents)	C++17	100 / 100	188 ms	35996 KB

tents

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 3030;
const int mod = 1e9 + 7;

using namespace std;

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

int d[N][N];

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < N; i++) {
        d[0][i] = d[i][0] = 1;
    }
    for (int i = 1; i < N; i++) {
        d[1][i] = d[i][1] = i * 4 + i * (i - 1) / 2 + 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            add(d[i][j], d[i - 1][j]);
            add(d[i][j], d[i - 1][j - 1] * 4ll % mod * j % mod);
            add(d[i][j], d[i - 1][j - 2] * (1ll * j * (j - 1) / 2 % mod) % mod);
            add(d[i][j], d[i - 2][j - 1] * (1ll * j * (i - 1) % mod) % mod);
        }
    }
    int res = d[n][m] - 1;
    if (res < 0) {
        res += mod;
    }
    cout << res << "\n";
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	12500 KB	Output is correct
2	Correct	5 ms	12500 KB	Output is correct
3	Correct	5 ms	12500 KB	Output is correct
4	Correct	5 ms	12500 KB	Output is correct
5	Correct	5 ms	12500 KB	Output is correct
6	Correct	6 ms	12500 KB	Output is correct
7	Correct	5 ms	12592 KB	Output is correct
8	Correct	6 ms	12500 KB	Output is correct
9	Correct	5 ms	12500 KB	Output is correct
10	Correct	5 ms	12596 KB	Output is correct
11	Correct	5 ms	12432 KB	Output is correct
12	Correct	6 ms	12756 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	12500 KB	Output is correct
2	Correct	5 ms	12500 KB	Output is correct
3	Correct	5 ms	12500 KB	Output is correct
4	Correct	5 ms	12500 KB	Output is correct
5	Correct	5 ms	12500 KB	Output is correct
6	Correct	6 ms	12500 KB	Output is correct
7	Correct	5 ms	12592 KB	Output is correct
8	Correct	6 ms	12500 KB	Output is correct
9	Correct	5 ms	12500 KB	Output is correct
10	Correct	5 ms	12596 KB	Output is correct
11	Correct	5 ms	12432 KB	Output is correct
12	Correct	6 ms	12756 KB	Output is correct
13	Correct	5 ms	12500 KB	Output is correct
14	Correct	5 ms	12468 KB	Output is correct
15	Correct	122 ms	34052 KB	Output is correct
16	Correct	12 ms	13780 KB	Output is correct
17	Correct	31 ms	17328 KB	Output is correct
18	Correct	37 ms	18436 KB	Output is correct
19	Correct	141 ms	35280 KB	Output is correct
20	Correct	113 ms	31632 KB	Output is correct
21	Correct	77 ms	25420 KB	Output is correct
22	Correct	75 ms	25680 KB	Output is correct
23	Correct	44 ms	19772 KB	Output is correct
24	Correct	188 ms	35996 KB	Output is correct
25	Correct	141 ms	32772 KB	Output is correct
26	Correct	161 ms	34456 KB	Output is correct
27	Correct	179 ms	35276 KB	Output is correct