Submission #131176

#	Time	Username	Problem	Language	Result	Execution time	Memory
131176		arthurconmy	Kangaroo (CEOI16_kangaroo)	C++14	36 / 100	2060 ms	21824 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
 
const int p = 1000000007;
 
int dp[201][201][201][2]; // ...[0] is initially increasing
					   // ...[1] is initially decreasing
 
int main() 
{
	int n;
	cin>>n;
	
	int L,R;
	cin>>L>>R;
	
	dp[1][1][1][0]=1;
	dp[1][1][1][1]=1;
	dp[2][1][2][0]=1;
	dp[2][2][1][1]=1;
	
	for(int i=3; i<=n; i++)
	{
		for(int l=1; l<=i; l++)
		{
			for(int r=1; r<=i; r++)
			{
				if(l==r) continue;
				
				for(int j=1; j<=n; j++)
				{
					if(j==l || j==r) continue;
					
					if(j<l)
					{
						dp[i][l][r][1] += dp[i-1][j][r-int(r>l)][0];
						dp[i][l][r][1] %= p;
					}
					
					if(j>l)
					{
						dp[i][l][r][0] += dp[i-1][j-1][r-int(r>l)][1];
						dp[i][l][r][0] %= p;
					}
				}
				
				// cout << i << " " << l << " " << r << " " << dp[i][l][r][0]+dp[i][l][r][1] << endl;
			}
		}
	}
	
	cout << (dp[n][L][R][0]+dp[n][L][R][1])%p << endl;
}

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