Submission #1077677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077677	2024-08-27T08:34:02 Z	rado	Tents (JOI18_tents)	C++14	100 / 100	52 ms	70740 KB

tents

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

void fastIO(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int MOD = 1e9+7;
long long dp[3001][3001];

int main(){
    fastIO();
    int n, m; cin>>n>>m;
    for(int i=0; i<=n; i++)dp[i][0] = 1;
    for(int j=0; j<=m; j++)dp[0][j] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = dp[i-1][j] + 4*j*dp[i-1][j-1];
            if(j >= 2)dp[i][j] += dp[i-1][j-2]*j*(j-1)/2;
            if(i >= 2)dp[i][j] += dp[i-2][j-1]*j*(i-1);
            dp[i][j] %= MOD;
        }
    }
    cout<<dp[n][m]-1<<endl;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	6504 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8620 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	6504 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8620 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	8540 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	5 ms	31836 KB	Output is correct
15	Correct	37 ms	58996 KB	Output is correct
16	Correct	2 ms	6492 KB	Output is correct
17	Correct	6 ms	17016 KB	Output is correct
18	Correct	8 ms	27228 KB	Output is correct
19	Correct	41 ms	65184 KB	Output is correct
20	Correct	36 ms	54108 KB	Output is correct
21	Correct	19 ms	37464 KB	Output is correct
22	Correct	23 ms	43212 KB	Output is correct
23	Correct	16 ms	43612 KB	Output is correct
24	Correct	52 ms	70740 KB	Output is correct
25	Correct	40 ms	61268 KB	Output is correct
26	Correct	43 ms	66640 KB	Output is correct
27	Correct	46 ms	68948 KB	Output is correct