Submission #51370

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51370	2018-06-17T17:28:57 Z	spencercompton	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	180 ms	32304 KB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, cs, cf;
ll mod = 1000000007LL;
ll dp[2001][2001];
ll go(int now, int blocks){
	if(now==n+1){
		if(blocks==1){
			return 1LL;
		}
		return 0LL;
	}
	if(dp[now][blocks]!=-1LL){
		return dp[now][blocks];
	}
	ll ret = 0LL;
	if(now==cs){
		if(now>cf){
			ret = go(now+1,blocks+1);
			if(blocks>1 && now<n){
				 ret += go(now+1,blocks)*(ll)(blocks-1);
			}
			if(now==n){
				ret += go(now+1,blocks);
			}
			ret %= mod;
		}
		else{
			ret = go(now+1,blocks+1);
			if(blocks>=1){
				ret += go(now+1,blocks)*(ll)blocks;
			}
			ret %= mod;
		}
	}
	else if(now==cf){
		if(now>cs){
			ret = go(now+1,blocks+1);
			if(blocks>1 && now<n){
				ret += go(now+1,blocks)*(blocks-1);
			}
			if(now==n){
				ret += go(now+1,blocks);
			}
			ret %= mod;
		}
		else{
			ret = go(now+1,blocks+1);
			if(blocks>=1){
				ret += go(now+1,blocks)*(ll)blocks;
			}
			ret %= mod;
		}
	}
	else{
		ret = go(now+1,blocks+1);
		int cnt = 0;
		if(now>cs){
			cnt++;
		}
		if(now>cf){
			cnt++;
		}
		if(cnt==0){
			//rand and then rand
			if(blocks>=2){
				ret += go(now+1,blocks-1) * ((blocks*(blocks-1))%mod);
				ret %= mod;
			}

		}
		else if(cnt==1){
			//rand and then rand
			if(blocks>=3){
				ret += go(now+1,blocks-1) * (((blocks-2)*(blocks-1))%mod);
				ret %= mod;
			}
			//imp and something
			if(blocks>=2){
				ret += go(now+1,blocks-1) * (blocks-1);
				ret %= mod;
			}

			
		}
		else{
			//rand and then rand
			if(blocks>=4){
				ret += go(now+1,blocks-1) * (((blocks-2)*(blocks-3))%mod);
				ret %= mod;
			}
			//imp and something
			if(blocks>=3){
				ret += 2LL * go(now+1,blocks-1) * (ll)(blocks-2);
				ret %= mod;
			}
			//imp and imp
			if(now==n){
				ret += go(now+1,blocks-1);
				ret %= mod;
			}
		}
	}
	dp[now][blocks] = ret;
	return ret;
}
int main(){
	cin >> n >> cs >> cf;
	for(int a = 0; a<=2000; a++){
		for(int b= 0; b<=2000; b++){
			dp[a][b] = -1LL;
		}
	}
	cout << go(1,0) << endl;

}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	31572 KB	Output is correct
2	Correct	24 ms	31744 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	31572 KB	Output is correct
2	Correct	24 ms	31744 KB	Output is correct
3	Correct	22 ms	31796 KB	Output is correct
4	Correct	23 ms	31796 KB	Output is correct
5	Correct	23 ms	31796 KB	Output is correct
6	Correct	23 ms	31880 KB	Output is correct
7	Correct	26 ms	31916 KB	Output is correct
8	Correct	25 ms	31952 KB	Output is correct
9	Correct	23 ms	31976 KB	Output is correct
10	Correct	25 ms	31996 KB	Output is correct
11	Correct	23 ms	32000 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	31572 KB	Output is correct
2	Correct	24 ms	31744 KB	Output is correct
3	Correct	22 ms	31796 KB	Output is correct
4	Correct	23 ms	31796 KB	Output is correct
5	Correct	23 ms	31796 KB	Output is correct
6	Correct	23 ms	31880 KB	Output is correct
7	Correct	26 ms	31916 KB	Output is correct
8	Correct	25 ms	31952 KB	Output is correct
9	Correct	23 ms	31976 KB	Output is correct
10	Correct	25 ms	31996 KB	Output is correct
11	Correct	23 ms	32000 KB	Output is correct
12	Correct	26 ms	32024 KB	Output is correct
13	Correct	25 ms	32024 KB	Output is correct
14	Correct	30 ms	32064 KB	Output is correct
15	Correct	25 ms	32112 KB	Output is correct
16	Correct	25 ms	32112 KB	Output is correct
17	Correct	25 ms	32112 KB	Output is correct
18	Correct	28 ms	32112 KB	Output is correct
19	Correct	26 ms	32112 KB	Output is correct
20	Correct	26 ms	32112 KB	Output is correct

Subtask #4

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	31572 KB	Output is correct
2	Correct	24 ms	31744 KB	Output is correct
3	Correct	22 ms	31796 KB	Output is correct
4	Correct	23 ms	31796 KB	Output is correct
5	Correct	23 ms	31796 KB	Output is correct
6	Correct	23 ms	31880 KB	Output is correct
7	Correct	26 ms	31916 KB	Output is correct
8	Correct	25 ms	31952 KB	Output is correct
9	Correct	23 ms	31976 KB	Output is correct
10	Correct	25 ms	31996 KB	Output is correct
11	Correct	23 ms	32000 KB	Output is correct
12	Correct	26 ms	32024 KB	Output is correct
13	Correct	25 ms	32024 KB	Output is correct
14	Correct	30 ms	32064 KB	Output is correct
15	Correct	25 ms	32112 KB	Output is correct
16	Correct	25 ms	32112 KB	Output is correct
17	Correct	25 ms	32112 KB	Output is correct
18	Correct	28 ms	32112 KB	Output is correct
19	Correct	26 ms	32112 KB	Output is correct
20	Correct	26 ms	32112 KB	Output is correct
21	Correct	40 ms	32152 KB	Output is correct
22	Correct	50 ms	32156 KB	Output is correct
23	Correct	45 ms	32288 KB	Output is correct
24	Correct	180 ms	32288 KB	Output is correct
25	Correct	140 ms	32304 KB	Output is correct
26	Correct	140 ms	32304 KB	Output is correct
27	Correct	160 ms	32304 KB	Output is correct
28	Correct	98 ms	32304 KB	Output is correct