| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 75647 |
2018-09-10T16:22:38 Z |
Andrei1998 |
Tents (JOI18_tents) |
C++17 |
|
106 ms |
35836 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);
}
}
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 |
476 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1360 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1620 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2000 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2000 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
476 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1360 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1620 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2000 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2000 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2144 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2144 KB |
Output is correct |
| 14 |
Correct |
8 ms |
9780 KB |
Output is correct |
| 15 |
Correct |
75 ms |
33120 KB |
Output is correct |
| 16 |
Correct |
7 ms |
33120 KB |
Output is correct |
| 17 |
Correct |
21 ms |
33120 KB |
Output is correct |
| 18 |
Correct |
23 ms |
33120 KB |
Output is correct |
| 19 |
Correct |
86 ms |
34912 KB |
Output is correct |
| 20 |
Correct |
69 ms |
34912 KB |
Output is correct |
| 21 |
Correct |
47 ms |
34912 KB |
Output is correct |
| 22 |
Correct |
49 ms |
34912 KB |
Output is correct |
| 23 |
Correct |
34 ms |
34912 KB |
Output is correct |
| 24 |
Correct |
106 ms |
35836 KB |
Output is correct |
| 25 |
Correct |
94 ms |
35836 KB |
Output is correct |
| 26 |
Correct |
100 ms |
35836 KB |
Output is correct |
| 27 |
Correct |
103 ms |
35836 KB |
Output is correct |
