Submission #833094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
833094	2023-08-22T00:16:47 Z	exodus_	Tents (JOI18_tents)	C++14	100 / 100	292 ms	125872 KB

tents

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long dp[4004][4004];
int main() {
    int n,m;
    cin >> n >> m;
    for(int i=0; i<4004; i++) {
        dp[0][i] = 1;
    }
    for(int i=1; i<4004; i++) {
        for(int j=0; j<4004; j++) {
            dp[i][j] += dp[i-1][j];
            if(j>=1) {
                dp[i][j] += ((dp[i-1][j-1] * j)%mod * 4)%mod;
                dp[i][j] %= mod;
            }
            if(j>=1 && i>=2) {
                dp[i][j] += ((dp[i-2][j-1] * j)%mod * (i-1))%mod;
                dp[i][j] %= mod;
            }
            if(i>=1 && j>=2) {
                dp[i][j] += (dp[i-1][j-2] * (j*(j-1)/2)%mod)%mod;
                dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][m]-1 << endl;
    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	260 ms	125860 KB	Output is correct
2	Correct	261 ms	125752 KB	Output is correct
3	Correct	266 ms	125664 KB	Output is correct
4	Correct	256 ms	125748 KB	Output is correct
5	Correct	255 ms	125660 KB	Output is correct
6	Correct	258 ms	125760 KB	Output is correct
7	Correct	262 ms	125872 KB	Output is correct
8	Correct	259 ms	125692 KB	Output is correct
9	Correct	257 ms	125784 KB	Output is correct
10	Correct	261 ms	125708 KB	Output is correct
11	Correct	269 ms	125772 KB	Output is correct
12	Correct	263 ms	125780 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	260 ms	125860 KB	Output is correct
2	Correct	261 ms	125752 KB	Output is correct
3	Correct	266 ms	125664 KB	Output is correct
4	Correct	256 ms	125748 KB	Output is correct
5	Correct	255 ms	125660 KB	Output is correct
6	Correct	258 ms	125760 KB	Output is correct
7	Correct	262 ms	125872 KB	Output is correct
8	Correct	259 ms	125692 KB	Output is correct
9	Correct	257 ms	125784 KB	Output is correct
10	Correct	261 ms	125708 KB	Output is correct
11	Correct	269 ms	125772 KB	Output is correct
12	Correct	263 ms	125780 KB	Output is correct
13	Correct	268 ms	125684 KB	Output is correct
14	Correct	292 ms	125752 KB	Output is correct
15	Correct	262 ms	125768 KB	Output is correct
16	Correct	257 ms	125704 KB	Output is correct
17	Correct	257 ms	125788 KB	Output is correct
18	Correct	261 ms	125760 KB	Output is correct
19	Correct	267 ms	125760 KB	Output is correct
20	Correct	263 ms	125764 KB	Output is correct
21	Correct	286 ms	125784 KB	Output is correct
22	Correct	263 ms	125712 KB	Output is correct
23	Correct	273 ms	125740 KB	Output is correct
24	Correct	266 ms	125768 KB	Output is correct
25	Correct	262 ms	125736 KB	Output is correct
26	Correct	263 ms	125764 KB	Output is correct
27	Correct	260 ms	125780 KB	Output is correct