#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2000;
const ll MOD = 1e9+7;
int N, S, E;
ll dp[MAXN+10][MAXN+10];
ll solve(int pos, int comp)
{
if(pos==N+1)
{
if(comp==1) return 1;
else return 0;
}
ll &ret=dp[pos][comp];
if(ret!=-1) return ret;
ret=0;
if(pos==S)
{
ret+=solve(pos+1, comp);
ret+=solve(pos+1, comp+1);
}
else if(pos==E)
{
ret+=solve(pos+1, comp);
ret+=solve(pos+1, comp+1);
}
else if(pos<S)
{
if(comp>=2) ret+=(comp-1)*solve(pos+1, comp-1);
ret+=(comp+1)*solve(pos+1, comp+1);
}
else if(pos<E)
{
if(comp>=2) ret+=(comp-1)*solve(pos+1, comp-1);
ret+=(comp)*solve(pos+1, comp+1);
}
else
{
if(comp>=2) ret+=(comp-1)*solve(pos+1, comp-1);
ret+=(comp-1)*solve(pos+1, comp+1);
}
ret%=MOD;
//printf("%d %d : %lld\n", pos, comp, ret);
return ret;
}
int main()
{
scanf("%d%d%d", &N, &S, &E); if(S>E) swap(S, E);
memset(dp, -1, sizeof(dp));
printf("%lld\n", solve(1, 0));
}
Compilation message
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
59 | scanf("%d%d%d", &N, &S, &E); if(S>E) swap(S, E);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31872 KB |
Output is correct |
2 |
Correct |
19 ms |
32000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31872 KB |
Output is correct |
2 |
Correct |
19 ms |
32000 KB |
Output is correct |
3 |
Correct |
19 ms |
31872 KB |
Output is correct |
4 |
Correct |
21 ms |
32000 KB |
Output is correct |
5 |
Correct |
20 ms |
32000 KB |
Output is correct |
6 |
Correct |
23 ms |
31872 KB |
Output is correct |
7 |
Correct |
19 ms |
31872 KB |
Output is correct |
8 |
Correct |
20 ms |
31872 KB |
Output is correct |
9 |
Correct |
19 ms |
31872 KB |
Output is correct |
10 |
Correct |
19 ms |
31872 KB |
Output is correct |
11 |
Correct |
20 ms |
32000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31872 KB |
Output is correct |
2 |
Correct |
19 ms |
32000 KB |
Output is correct |
3 |
Correct |
19 ms |
31872 KB |
Output is correct |
4 |
Correct |
21 ms |
32000 KB |
Output is correct |
5 |
Correct |
20 ms |
32000 KB |
Output is correct |
6 |
Correct |
23 ms |
31872 KB |
Output is correct |
7 |
Correct |
19 ms |
31872 KB |
Output is correct |
8 |
Correct |
20 ms |
31872 KB |
Output is correct |
9 |
Correct |
19 ms |
31872 KB |
Output is correct |
10 |
Correct |
19 ms |
31872 KB |
Output is correct |
11 |
Correct |
20 ms |
32000 KB |
Output is correct |
12 |
Correct |
20 ms |
31872 KB |
Output is correct |
13 |
Correct |
19 ms |
31920 KB |
Output is correct |
14 |
Correct |
21 ms |
32000 KB |
Output is correct |
15 |
Correct |
20 ms |
31992 KB |
Output is correct |
16 |
Correct |
20 ms |
32000 KB |
Output is correct |
17 |
Correct |
19 ms |
32000 KB |
Output is correct |
18 |
Correct |
19 ms |
32000 KB |
Output is correct |
19 |
Correct |
19 ms |
32000 KB |
Output is correct |
20 |
Correct |
19 ms |
32000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31872 KB |
Output is correct |
2 |
Correct |
19 ms |
32000 KB |
Output is correct |
3 |
Correct |
19 ms |
31872 KB |
Output is correct |
4 |
Correct |
21 ms |
32000 KB |
Output is correct |
5 |
Correct |
20 ms |
32000 KB |
Output is correct |
6 |
Correct |
23 ms |
31872 KB |
Output is correct |
7 |
Correct |
19 ms |
31872 KB |
Output is correct |
8 |
Correct |
20 ms |
31872 KB |
Output is correct |
9 |
Correct |
19 ms |
31872 KB |
Output is correct |
10 |
Correct |
19 ms |
31872 KB |
Output is correct |
11 |
Correct |
20 ms |
32000 KB |
Output is correct |
12 |
Correct |
20 ms |
31872 KB |
Output is correct |
13 |
Correct |
19 ms |
31920 KB |
Output is correct |
14 |
Correct |
21 ms |
32000 KB |
Output is correct |
15 |
Correct |
20 ms |
31992 KB |
Output is correct |
16 |
Correct |
20 ms |
32000 KB |
Output is correct |
17 |
Correct |
19 ms |
32000 KB |
Output is correct |
18 |
Correct |
19 ms |
32000 KB |
Output is correct |
19 |
Correct |
19 ms |
32000 KB |
Output is correct |
20 |
Correct |
19 ms |
32000 KB |
Output is correct |
21 |
Correct |
23 ms |
32032 KB |
Output is correct |
22 |
Correct |
23 ms |
32000 KB |
Output is correct |
23 |
Correct |
24 ms |
32036 KB |
Output is correct |
24 |
Correct |
70 ms |
32000 KB |
Output is correct |
25 |
Correct |
62 ms |
32000 KB |
Output is correct |
26 |
Correct |
66 ms |
32000 KB |
Output is correct |
27 |
Correct |
71 ms |
32120 KB |
Output is correct |
28 |
Correct |
44 ms |
32000 KB |
Output is correct |