oj.uz

Submission #51369

# Submission time Handle Problem Language Result Execution time Memory
51369 2018-06-17T17:25:29 Z spencercompton Kangaroo (CEOI16_kangaroo) C++17
6 / 100
 28 ms 31952 KB 
#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)*(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)*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);
		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 23 ms 31608 KB Output is correct
2 Correct 28 ms 31856 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31608 KB Output is correct
2 Correct 28 ms 31856 KB Output is correct
3 Correct 26 ms 31856 KB Output is correct
4 Correct 26 ms 31952 KB Output is correct
5 Incorrect 23 ms 31952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31608 KB Output is correct
2 Correct 28 ms 31856 KB Output is correct
3 Correct 26 ms 31856 KB Output is correct
4 Correct 26 ms 31952 KB Output is correct
5 Incorrect 23 ms 31952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31608 KB Output is correct
2 Correct 28 ms 31856 KB Output is correct
3 Correct 26 ms 31856 KB Output is correct
4 Correct 26 ms 31952 KB Output is correct
5 Incorrect 23 ms 31952 KB Output isn't correct
6 Halted 0 ms 0 KB -