답안 #887907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887907	2023-12-15T12:58:59 Z	vjudge1	Tents (JOI18_tents)	C++17	100 / 100	56 ms	71040 KB

tents

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 3e3 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

int n , m , dp[maxn][maxn];

int32_t main(){
    ios_base::sync_with_stdio(false);

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

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	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	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8536 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	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	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8536 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	6 ms	55644 KB	Output is correct
15	Correct	37 ms	66136 KB	Output is correct
16	Correct	4 ms	6744 KB	Output is correct
17	Correct	9 ms	16988 KB	Output is correct
18	Correct	12 ms	29276 KB	Output is correct
19	Correct	43 ms	70380 KB	Output is correct
20	Correct	35 ms	59996 KB	Output is correct
21	Correct	23 ms	39516 KB	Output is correct
22	Correct	24 ms	51800 KB	Output is correct
23	Correct	20 ms	70492 KB	Output is correct
24	Correct	56 ms	71040 KB	Output is correct
25	Correct	44 ms	62044 KB	Output is correct
26	Correct	52 ms	68440 KB	Output is correct
27	Correct	53 ms	70380 KB	Output is correct