제출 #131160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131160		arthurconmy	캥거루 (CEOI16_kangaroo)	C++14	6 / 100	8 ms	632 KiB

kangaroo

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

const int p = 1000000007;

int dp[41][41][41][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] << endl;
}

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