| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1082752 |
2024-09-01T13:03:00 Z |
toast12 |
Tents (JOI18_tents) |
C++14 |
|
211 ms |
72596 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
vector<vector<bool>> ready;
vector<vector<ll>> dp;
// there are h rows and w columns left
ll solve(int h, int w) {
if (h < 0 || w < 0)
return 0;
if (h == 0 || w == 0)
return 1;
if (ready[h][w])
return dp[h][w];
ll ans = 0;
// place nothing
ans += solve(h-1, w);
ans %= MOD;
// place one tent in this row
// this eliminates one row, one column, and there are 4 different directions the opening can be
ans += 4*solve(h-1, w-1)*w;
ans %= MOD;
// place two tents in this row
// this eliminates one row, two columns and you can place the two tents in w choose 2 different ways
ans += solve(h-1, w-2)*(w*(w-1)/2);
ans %= MOD;
// place two tents in one column, but one of them is in this row
// this eliminates two rows, one column and you can choose the column w ways and choose the other row (h-1) ways
ans += solve(h-2, w-1)*w*(h-1);
ans %= MOD;
ready[h][w] = true;
return dp[h][w] = ans;
}
int main() {
int h, w;
cin >> h >> w;
ready.resize(h+1, vector<bool>(w+1));
dp.resize(h+1, vector<ll>(w+1));
cout << (solve(h, w)+MOD-1) % MOD << '\n';
return 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 |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 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 |
440 KB |
Output is correct |
| 8 |
Correct |
2 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 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 |
3 ms |
1120 KB |
Output is correct |
| # |
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 |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 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 |
440 KB |
Output is correct |
| 8 |
Correct |
2 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 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 |
3 ms |
1120 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
136 ms |
45456 KB |
Output is correct |
| 16 |
Correct |
3 ms |
3224 KB |
Output is correct |
| 17 |
Correct |
16 ms |
10496 KB |
Output is correct |
| 18 |
Correct |
35 ms |
12892 KB |
Output is correct |
| 19 |
Correct |
178 ms |
52828 KB |
Output is correct |
| 20 |
Correct |
132 ms |
42332 KB |
Output is correct |
| 21 |
Correct |
64 ms |
27972 KB |
Output is correct |
| 22 |
Correct |
85 ms |
27576 KB |
Output is correct |
| 23 |
Correct |
55 ms |
15704 KB |
Output is correct |
| 24 |
Correct |
211 ms |
72596 KB |
Output is correct |
| 25 |
Correct |
148 ms |
54008 KB |
Output is correct |
| 26 |
Correct |
178 ms |
61860 KB |
Output is correct |
| 27 |
Correct |
208 ms |
69804 KB |
Output is correct |
