| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 75649 |
2018-09-10T16:23:26 Z |
Andrei1998 |
Tents (JOI18_tents) |
C++17 |
|
107 ms |
35964 KB |
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000000 + 7;
inline void add(int &where, const int val) {
where += val;
if (where >= MOD)
where -= MOD;
}
const int NMAX = 3000 + 5;
int N, M;
int dp[NMAX][NMAX];
int main() {
cin >> N >> M;
for (int n = 0; n <= N; ++n) {
for (int m = 0; m <= M; ++m) {
if (n == 0 || m == 0) {
dp[n][m] = 1;
continue;
}
dp[n][m] = dp[n - 1][m]; // No tents on the first row
add(dp[n][m], (4LL * m * dp[n - 1][m - 1]) % MOD); // A single tent on the first row and none on its column
if (n >= 2)
add(dp[n][m], (m * (n - 1LL) * dp[n - 2][m - 1]) % MOD); // A single tent on the first row and one more on its column
if (m >= 2)
add(dp[n][m], (m * (m - 1LL) / 2 * dp[n - 1][m - 2]) % MOD); // Two tents on the first row and none on their columns
}
}
cout << (dp[N][M] + MOD - 1) % MOD << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1252 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1252 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1568 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1568 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1660 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1916 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1916 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1252 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1252 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1568 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1568 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1660 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1916 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1916 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2172 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2172 KB |
Output is correct |
| 14 |
Correct |
8 ms |
9852 KB |
Output is correct |
| 15 |
Correct |
76 ms |
33148 KB |
Output is correct |
| 16 |
Correct |
8 ms |
33148 KB |
Output is correct |
| 17 |
Correct |
18 ms |
33148 KB |
Output is correct |
| 18 |
Correct |
23 ms |
33148 KB |
Output is correct |
| 19 |
Correct |
87 ms |
34812 KB |
Output is correct |
| 20 |
Correct |
72 ms |
34812 KB |
Output is correct |
| 21 |
Correct |
46 ms |
34812 KB |
Output is correct |
| 22 |
Correct |
47 ms |
34812 KB |
Output is correct |
| 23 |
Correct |
32 ms |
34812 KB |
Output is correct |
| 24 |
Correct |
107 ms |
35964 KB |
Output is correct |
| 25 |
Correct |
88 ms |
35964 KB |
Output is correct |
| 26 |
Correct |
96 ms |
35964 KB |
Output is correct |
| 27 |
Correct |
104 ms |
35964 KB |
Output is correct |
