Submission #914379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914379	2024-01-21T19:29:01 Z	Andrey	Tents (JOI18_tents)	C++14	100 / 100	73 ms	70748 KB

tents

#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9+7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,m;
    cin >> n >> m;
    long long dp[n+1][m+1];
    for(long long i = 0; i <= m; i++) {
        dp[0][i] = 1;
    }
    for(long long i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= m; j++) {
            dp[i][j] = 0;
            dp[i][j]+=dp[i-1][j];
            if(j >= 2) {
                dp[i][j]+=(((j*(j-1)/2))%MOD)*dp[i-1][j-2];
            }
            dp[i][j]+=4*j*dp[i-1][j-1];
            if(i >= 2) {
                dp[i][j]+=j*(i-1)*dp[i-2][j-1];
            }
            dp[i][j]%=MOD;
        }
    }
    cout << (dp[n][m]-1+MOD)%MOD;
    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	47 ms	44204 KB	Output is correct
16	Correct	3 ms	3160 KB	Output is correct
17	Correct	10 ms	10072 KB	Output is correct
18	Correct	13 ms	12380 KB	Output is correct
19	Correct	53 ms	51292 KB	Output is correct
20	Correct	42 ms	41040 KB	Output is correct
21	Correct	29 ms	27228 KB	Output is correct
22	Correct	29 ms	26716 KB	Output is correct
23	Correct	15 ms	14940 KB	Output is correct
24	Correct	73 ms	70748 KB	Output is correct
25	Correct	60 ms	52664 KB	Output is correct
26	Correct	62 ms	60240 KB	Output is correct
27	Correct	69 ms	68168 KB	Output is correct