# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
813808 |
2023-08-08T04:01:36 Z |
andecaandeci |
Tents (JOI18_tents) |
C++17 |
|
295 ms |
217096 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 3e2 + 5;
const int mod = 1e9 + 7;
ll dp[N][N][N];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int h, w;
cin >> h >> w;
dp[0][w][0] = 1;
for (int i = 0; i < h; i++) {
for (int j = w; j >= 0; j--) {
for (int k = h; k >= 0; k--) {
if (j >= 2) {
dp[i + 1][j - 2][k] += j * (j - 1) / 2 * dp[i][j][k];
dp[i + 1][j - 2][k] %= mod;
}
if (j >= 1) {
dp[i + 1][j - 1][k] += 4 * j * dp[i][j][k];
dp[i + 1][j - 1][k] %= mod;
if (k >= 1) {
dp[i + 1][j - 1][k - 1] += ((j * k) % mod) * dp[i][j][k];
dp[i + 1][j - 1][k - 1] %= mod;
}
}
dp[i + 1][j][k + 1] += dp[i][j][k];
dp[i + 1][j][k + 1] %= mod;
}
}
}
ll ans = 0;
for (int i = 0; i < w; i++) {
for (int j = 0; j <= h; j++) {
ans += dp[h][i][j];
ans %= mod;
}
}
cout << ans << "\n";
// for (int i = 0; i <= h; i++) {
// for (int j = 0; j <= w; j++) {
// cout << i << " " << j << "gvawp\n";
// for (int k = 0; k <= w; k++) cout << dp[i][j][k] << " ";
// cout << "\n";
// }
// }
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
29 ms |
38408 KB |
Output is correct |
6 |
Correct |
58 ms |
49112 KB |
Output is correct |
7 |
Correct |
39 ms |
47828 KB |
Output is correct |
8 |
Correct |
47 ms |
36672 KB |
Output is correct |
9 |
Correct |
2 ms |
2260 KB |
Output is correct |
10 |
Correct |
139 ms |
97872 KB |
Output is correct |
11 |
Correct |
5 ms |
7508 KB |
Output is correct |
12 |
Correct |
295 ms |
217096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
29 ms |
38408 KB |
Output is correct |
6 |
Correct |
58 ms |
49112 KB |
Output is correct |
7 |
Correct |
39 ms |
47828 KB |
Output is correct |
8 |
Correct |
47 ms |
36672 KB |
Output is correct |
9 |
Correct |
2 ms |
2260 KB |
Output is correct |
10 |
Correct |
139 ms |
97872 KB |
Output is correct |
11 |
Correct |
5 ms |
7508 KB |
Output is correct |
12 |
Correct |
295 ms |
217096 KB |
Output is correct |
13 |
Incorrect |
3 ms |
4692 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |