| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 75646 |
2018-09-10T16:21:49 Z |
Andrei1998 |
Tents (JOI18_tents) |
C++17 |
|
121 ms |
35968 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 the on 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 the on 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);
}
}
cout << (dp[N][M] + MOD - 1) % MOD << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
552 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1196 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1196 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1444 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1692 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1692 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2000 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2000 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
552 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1196 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1196 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1444 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1692 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1692 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2000 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2000 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2180 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2180 KB |
Output is correct |
| 14 |
Correct |
9 ms |
9996 KB |
Output is correct |
| 15 |
Correct |
79 ms |
33092 KB |
Output is correct |
| 16 |
Correct |
7 ms |
33092 KB |
Output is correct |
| 17 |
Correct |
21 ms |
33092 KB |
Output is correct |
| 18 |
Correct |
24 ms |
33092 KB |
Output is correct |
| 19 |
Correct |
88 ms |
34964 KB |
Output is correct |
| 20 |
Correct |
69 ms |
34964 KB |
Output is correct |
| 21 |
Correct |
48 ms |
34964 KB |
Output is correct |
| 22 |
Correct |
52 ms |
34964 KB |
Output is correct |
| 23 |
Correct |
32 ms |
34964 KB |
Output is correct |
| 24 |
Correct |
121 ms |
35968 KB |
Output is correct |
| 25 |
Correct |
84 ms |
35968 KB |
Output is correct |
| 26 |
Correct |
93 ms |
35968 KB |
Output is correct |
| 27 |
Correct |
105 ms |
35968 KB |
Output is correct |
