Submission #132824

#	Time	Username	Problem	Language	Result	Execution time	Memory
132824		arthurconmy	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	106 ms	65784 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() 
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	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][2][0]=1; // 'extra' base case for the cumulative DP

	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++)
			{
				dp[i][l][r][0] = dp[i][l-1][r][0];
				dp[i][l][r][1] = dp[i][l-1][r][1];

				if(l==r) continue;

				dp[i][l][r][1] += dp[i-1][l-1][r-int(r>l)][0];
				dp[i][l][r][1] %= p;

				dp[i][l][r][0] += dp[i-1][i-1][r-int(r>l)][1];
				dp[i][l][r][0] %= p;

				dp[i][l][r][0] += p - dp[i-1][l-1][r-int(r>l)][1];
				dp[i][l][r][0] %= p;

				int cur = dp[i][l][r][0] + dp[i][l][r][1];
				cur%=p;

				cur += p-dp[i][l-1][r][0];
				cur%=p;

				cur += p-dp[i][l-1][r][1];
				cur %= p;

				//cout << i << " " << l << " " << r << " " << cur << endl;

				// if(i==4 && l==3 && r==2) cout << dp[i][l][r][0] << " " << dp[i][l][r][1] << endl;
			}
		}
	}
	
	int cur = dp[n][L][R][0] + dp[n][L][R][1];
	cur%=p;

	cur += p-dp[n][L-1][R][0];
	cur%=p;

	cur += p-dp[n][L-1][R][1];
	cur %= p;	

	cout << cur << endl;
}
	

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