Submission #110564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
110564	2019-05-11T07:21:18 Z	gumball	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	149 ms	32408 KB

kangaroo

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,S,T,d[2020][2020],mo=1e9+7;
ll depe(ll aa,ll bb)
{
	if(aa==(n+1)&&bb==1)return 1;
	if(aa==(n+1))return 0;
	if(bb<0)return 0;
	ll ret=d[aa][bb];
	if(ret!=-1)return ret;
	ret=0;
	ll ujg=0;
	if(aa>S)ujg++;
	if(aa>T)ujg++;
	if(aa==S||aa==T)
	{
		ret=(depe(aa+1,bb+1)+depe(aa+1,bb))%mo;
	}	
	else
	{	
		ret=(ret+depe(aa+1,bb+1)*(bb+1-ujg))%mo;
		ret=(ret+depe(aa+1,bb-1)*(bb-1))%mo;
	}
	return d[aa][bb]=ret;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>S>>T;
	memset(d,-1,sizeof(d));
	if(n==2)cout<<1<<"\n";
	else
		cout<<depe(1,0)<<"\n";
}	

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	32256 KB	Output is correct
2	Correct	26 ms	32248 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	32256 KB	Output is correct
2	Correct	26 ms	32248 KB	Output is correct
3	Correct	31 ms	32248 KB	Output is correct
4	Correct	25 ms	32220 KB	Output is correct
5	Correct	28 ms	32376 KB	Output is correct
6	Correct	25 ms	32248 KB	Output is correct
7	Correct	29 ms	32248 KB	Output is correct
8	Correct	28 ms	32256 KB	Output is correct
9	Correct	30 ms	32248 KB	Output is correct
10	Correct	26 ms	32248 KB	Output is correct
11	Correct	31 ms	32256 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	32256 KB	Output is correct
2	Correct	26 ms	32248 KB	Output is correct
3	Correct	31 ms	32248 KB	Output is correct
4	Correct	25 ms	32220 KB	Output is correct
5	Correct	28 ms	32376 KB	Output is correct
6	Correct	25 ms	32248 KB	Output is correct
7	Correct	29 ms	32248 KB	Output is correct
8	Correct	28 ms	32256 KB	Output is correct
9	Correct	30 ms	32248 KB	Output is correct
10	Correct	26 ms	32248 KB	Output is correct
11	Correct	31 ms	32256 KB	Output is correct
12	Correct	26 ms	32256 KB	Output is correct
13	Correct	33 ms	32248 KB	Output is correct
14	Correct	27 ms	32220 KB	Output is correct
15	Correct	26 ms	32252 KB	Output is correct
16	Correct	27 ms	32256 KB	Output is correct
17	Correct	32 ms	32256 KB	Output is correct
18	Correct	28 ms	32248 KB	Output is correct
19	Correct	30 ms	32288 KB	Output is correct
20	Correct	29 ms	32256 KB	Output is correct

Subtask #4

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	32256 KB	Output is correct
2	Correct	26 ms	32248 KB	Output is correct
3	Correct	31 ms	32248 KB	Output is correct
4	Correct	25 ms	32220 KB	Output is correct
5	Correct	28 ms	32376 KB	Output is correct
6	Correct	25 ms	32248 KB	Output is correct
7	Correct	29 ms	32248 KB	Output is correct
8	Correct	28 ms	32256 KB	Output is correct
9	Correct	30 ms	32248 KB	Output is correct
10	Correct	26 ms	32248 KB	Output is correct
11	Correct	31 ms	32256 KB	Output is correct
12	Correct	26 ms	32256 KB	Output is correct
13	Correct	33 ms	32248 KB	Output is correct
14	Correct	27 ms	32220 KB	Output is correct
15	Correct	26 ms	32252 KB	Output is correct
16	Correct	27 ms	32256 KB	Output is correct
17	Correct	32 ms	32256 KB	Output is correct
18	Correct	28 ms	32248 KB	Output is correct
19	Correct	30 ms	32288 KB	Output is correct
20	Correct	29 ms	32256 KB	Output is correct
21	Correct	37 ms	32324 KB	Output is correct
22	Correct	42 ms	32324 KB	Output is correct
23	Correct	56 ms	32376 KB	Output is correct
24	Correct	139 ms	32404 KB	Output is correct
25	Correct	126 ms	32408 KB	Output is correct
26	Correct	141 ms	32408 KB	Output is correct
27	Correct	149 ms	32384 KB	Output is correct
28	Correct	94 ms	32376 KB	Output is correct