Submission #706286

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706286	2023-03-06T08:55:34 Z	lukameladze	Tents (JOI18_tents)	C++14	100 / 100	121 ms	70860 KB

tents

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
using namespace std;
const int N = 3005, mod = 1e9 + 7;
int n, m, dp[N][N];
int C(int n, int k) {
    return n * (n - 1) / 2;
}
main() {
    cin>>n>>m;
    for (int i = 0; i <= max(n,m); i++) dp[0][i] = dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] += dp[i - 1][j];
            if (j >= 2) dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * C(j, 2)) % mod;
            dp[i][j] = (dp[i][j] + (dp[i - 1][j - 1] * 4 * j) % mod) % mod; 
            if (i >= 2) dp[i][j] += dp[i - 2][j - 1] * j * (i - 1) % mod;
            dp[i][j] %= mod;
        }
    }
    dp[n][m] = (dp[n][m] - 1 + mod) % mod;
    cout<<dp[n][m]<<"\n";
}

Compilation message

tents.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	1460 KB	Output is correct
6	Correct	1 ms	1336 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	736 KB	Output is correct
10	Correct	2 ms	1720 KB	Output is correct
11	Correct	1 ms	1492 KB	Output is correct
12	Correct	2 ms	2132 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	1460 KB	Output is correct
6	Correct	1 ms	1336 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	736 KB	Output is correct
10	Correct	2 ms	1720 KB	Output is correct
11	Correct	1 ms	1492 KB	Output is correct
12	Correct	2 ms	2132 KB	Output is correct
13	Correct	3 ms	7764 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	72 ms	55164 KB	Output is correct
16	Correct	7 ms	9428 KB	Output is correct
17	Correct	18 ms	17324 KB	Output is correct
18	Correct	22 ms	17792 KB	Output is correct
19	Correct	83 ms	62924 KB	Output is correct
20	Correct	66 ms	50848 KB	Output is correct
21	Correct	45 ms	35404 KB	Output is correct
22	Correct	47 ms	35404 KB	Output is correct
23	Correct	34 ms	27016 KB	Output is correct
24	Correct	107 ms	70860 KB	Output is correct
25	Correct	83 ms	61164 KB	Output is correct
26	Correct	94 ms	66600 KB	Output is correct
27	Correct	121 ms	69168 KB	Output is correct