#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 2010;
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int n;
int ini, fim;
int solve(int i, int k) {
if (i == n+1) return (k==1);
if (dp[i][k] != -1) return dp[i][k];
int caso1, caso2;
if (i == ini || i == fim) {
caso1 = solve(i+1, k+1);
caso2 = k > 0 ? solve(i+1, k) : 0;
} else if (i < ini && i < fim) {
caso1 = (k+1) * solve(i+1, k+1);
caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
} else if (i < ini || i < fim) {
caso1 = k * solve(i+1, k+1);
caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
} else {
caso1 = (k-1) * solve(i+1, k+1);
caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
}
return dp[i][k] = (caso1 + caso2) % mod;
}
int32_t main() {
memset(dp, -1, sizeof dp);
cin >> n;
cin >> ini >> fim;
cout << solve(1, 0) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31980 KB |
Output is correct |
2 |
Correct |
17 ms |
31980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31980 KB |
Output is correct |
2 |
Correct |
17 ms |
31980 KB |
Output is correct |
3 |
Correct |
17 ms |
31980 KB |
Output is correct |
4 |
Correct |
17 ms |
31852 KB |
Output is correct |
5 |
Correct |
18 ms |
31980 KB |
Output is correct |
6 |
Correct |
18 ms |
32000 KB |
Output is correct |
7 |
Correct |
18 ms |
31980 KB |
Output is correct |
8 |
Correct |
18 ms |
31980 KB |
Output is correct |
9 |
Correct |
18 ms |
31980 KB |
Output is correct |
10 |
Correct |
18 ms |
31980 KB |
Output is correct |
11 |
Correct |
18 ms |
31980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31980 KB |
Output is correct |
2 |
Correct |
17 ms |
31980 KB |
Output is correct |
3 |
Correct |
17 ms |
31980 KB |
Output is correct |
4 |
Correct |
17 ms |
31852 KB |
Output is correct |
5 |
Correct |
18 ms |
31980 KB |
Output is correct |
6 |
Correct |
18 ms |
32000 KB |
Output is correct |
7 |
Correct |
18 ms |
31980 KB |
Output is correct |
8 |
Correct |
18 ms |
31980 KB |
Output is correct |
9 |
Correct |
18 ms |
31980 KB |
Output is correct |
10 |
Correct |
18 ms |
31980 KB |
Output is correct |
11 |
Correct |
18 ms |
31980 KB |
Output is correct |
12 |
Correct |
19 ms |
31980 KB |
Output is correct |
13 |
Correct |
18 ms |
31980 KB |
Output is correct |
14 |
Correct |
18 ms |
31980 KB |
Output is correct |
15 |
Correct |
17 ms |
31980 KB |
Output is correct |
16 |
Correct |
18 ms |
31980 KB |
Output is correct |
17 |
Correct |
18 ms |
31980 KB |
Output is correct |
18 |
Correct |
18 ms |
31980 KB |
Output is correct |
19 |
Correct |
17 ms |
31980 KB |
Output is correct |
20 |
Correct |
17 ms |
31980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31980 KB |
Output is correct |
2 |
Correct |
17 ms |
31980 KB |
Output is correct |
3 |
Correct |
17 ms |
31980 KB |
Output is correct |
4 |
Correct |
17 ms |
31852 KB |
Output is correct |
5 |
Correct |
18 ms |
31980 KB |
Output is correct |
6 |
Correct |
18 ms |
32000 KB |
Output is correct |
7 |
Correct |
18 ms |
31980 KB |
Output is correct |
8 |
Correct |
18 ms |
31980 KB |
Output is correct |
9 |
Correct |
18 ms |
31980 KB |
Output is correct |
10 |
Correct |
18 ms |
31980 KB |
Output is correct |
11 |
Correct |
18 ms |
31980 KB |
Output is correct |
12 |
Correct |
19 ms |
31980 KB |
Output is correct |
13 |
Correct |
18 ms |
31980 KB |
Output is correct |
14 |
Correct |
18 ms |
31980 KB |
Output is correct |
15 |
Correct |
17 ms |
31980 KB |
Output is correct |
16 |
Correct |
18 ms |
31980 KB |
Output is correct |
17 |
Correct |
18 ms |
31980 KB |
Output is correct |
18 |
Correct |
18 ms |
31980 KB |
Output is correct |
19 |
Correct |
17 ms |
31980 KB |
Output is correct |
20 |
Correct |
17 ms |
31980 KB |
Output is correct |
21 |
Correct |
21 ms |
31980 KB |
Output is correct |
22 |
Correct |
21 ms |
31980 KB |
Output is correct |
23 |
Correct |
22 ms |
32000 KB |
Output is correct |
24 |
Correct |
50 ms |
32108 KB |
Output is correct |
25 |
Correct |
49 ms |
32108 KB |
Output is correct |
26 |
Correct |
51 ms |
32108 KB |
Output is correct |
27 |
Correct |
52 ms |
32108 KB |
Output is correct |
28 |
Correct |
34 ms |
31980 KB |
Output is correct |