Submission #938756

#	Time	Username	Problem	Language	Result	Execution time	Memory
938756		Doncho_Bonboncho	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	13 ms	32348 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0; }
template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0; }

#ifndef LOCAL
#define cerr if( false )cerr
#endif

#define out(x) #x << " = " << x << "  "

typedef long long ll;

const int MAX_N = 2048;
const ll mod = 1e9 + 7;

ll dp[MAX_N][MAX_N];

int main (){

#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n, S, E;
	std::cin >> n >> S >> E;

	dp[1][1] = 1;
	for( int i=2 ; i <= n ; i++ ){
		for( int j=1 ; j <= i ; j ++ ){
			if( i == S || i == E ){
				dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j] ) % mod;
			}else{
				dp[i][j] = ( dp[i-1][j+1] * j ) % mod;
				dp[i][j] += ( dp[i-1][j-1] * ( j - ( S < i ) - ( E < i ) ) ) %mod;
				if( dp[i][j] >= mod ) dp[i][j] -= mod;
			}
		}
	}
	
	std::cout << dp[n][1] << endl;
	
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49