Submission #781373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781373	2023-07-13T04:51:06 Z	이동현(#10013)	Tents (JOI18_tents)	C++17	100 / 100	141 ms	117364 KB

tents

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int mod = (int)1e9 + 7;
int n, m;
int comb[3004][3004];
int dp[3004][3004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < 3004; ++i){
        comb[i][0] = 1;
        for(int j = 1; j <= i; ++j){
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
        }
    }

    dp[0][0] = 1;
    for(int i = 1; i < 3004; ++i){
        for(int j = 1; j < 3004; ++j){
            dp[i][j] = j * dp[i - 1][j - 1] % mod * 4 % mod;
            if(j > 1){
                (dp[i][j] += j * (j - 1) / 2 % mod * dp[i - 1][j - 2]) %= mod;
            }
            if(i > 1){
                (dp[i][j] += j * (i - 1) % mod * dp[i - 2][j - 1]) %= mod;
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            (ans += comb[n][i] * comb[m][j] % mod * dp[i][j] % mod) %= mod;
        }
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	117204 KB	Output is correct
2	Correct	100 ms	117140 KB	Output is correct
3	Correct	100 ms	117168 KB	Output is correct
4	Correct	101 ms	117188 KB	Output is correct
5	Correct	100 ms	117196 KB	Output is correct
6	Correct	107 ms	117244 KB	Output is correct
7	Correct	100 ms	117196 KB	Output is correct
8	Correct	99 ms	117168 KB	Output is correct
9	Correct	101 ms	117168 KB	Output is correct
10	Correct	118 ms	117148 KB	Output is correct
11	Correct	102 ms	117236 KB	Output is correct
12	Correct	101 ms	117188 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	117204 KB	Output is correct
2	Correct	100 ms	117140 KB	Output is correct
3	Correct	100 ms	117168 KB	Output is correct
4	Correct	101 ms	117188 KB	Output is correct
5	Correct	100 ms	117196 KB	Output is correct
6	Correct	107 ms	117244 KB	Output is correct
7	Correct	100 ms	117196 KB	Output is correct
8	Correct	99 ms	117168 KB	Output is correct
9	Correct	101 ms	117168 KB	Output is correct
10	Correct	118 ms	117148 KB	Output is correct
11	Correct	102 ms	117236 KB	Output is correct
12	Correct	101 ms	117188 KB	Output is correct
13	Correct	102 ms	117172 KB	Output is correct
14	Correct	101 ms	117184 KB	Output is correct
15	Correct	129 ms	117364 KB	Output is correct
16	Correct	105 ms	117160 KB	Output is correct
17	Correct	117 ms	117200 KB	Output is correct
18	Correct	107 ms	117256 KB	Output is correct
19	Correct	129 ms	117220 KB	Output is correct
20	Correct	124 ms	117208 KB	Output is correct
21	Correct	116 ms	117248 KB	Output is correct
22	Correct	115 ms	117192 KB	Output is correct
23	Correct	130 ms	117180 KB	Output is correct
24	Correct	141 ms	117288 KB	Output is correct
25	Correct	130 ms	117240 KB	Output is correct
26	Correct	134 ms	117196 KB	Output is correct
27	Correct	137 ms	117248 KB	Output is correct