Submission #30654

#	Time	Username	Problem	Language	Result	Execution time	Memory
30654		zscoder	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	73 ms	17820 KiB

kangaroo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const int MOD = 1e9 + 7;

void add(int &a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
}

int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

int dp[2001][2001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,s,e;
	cin>>n>>s>>e;
	s--; e--;
	if(s==0)
	{
		dp[0][0]=1;
	}
	else if(e==0)
	{
		dp[0][0]=1;
	}
	else
	{
		dp[0][1]=1;
	}
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(dp[i][j]!=0)
			{
				//cerr<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
				int v=dp[i][j];
				if(i+1==n-1)
				{
					add(dp[i+1][j],v);
					continue;
				}
				if(i+1==s)
				{
					//just add
					add(dp[i+1][j],v);
					//combine with free
					if(j>=1) add(dp[i+1][j-1],mult(j,v));
				}
				else if(i+1==e)
				{
					//just add
					add(dp[i+1][j],v);
					//combine with free
					if(j>=1) add(dp[i+1][j-1],mult(j,v));
				}
				else
				{
					//new component
					add(dp[i+1][j+1],v);
					//merge two free components
					if(j>=2) add(dp[i+1][j-1],mult(j*(j-1),v));
					//append to starting component
					if(i+1>=s)
					{
						//add(dp[i+1][j],v);
						//merge starting with free
						if(j>=1)
						{
							add(dp[i+1][j-1],mult(j,v));
						}
					}
					//append to ending component
					if(i+1>=e)
					{
						//add(dp[i+1][j],v);
						//merge ending with free
						if(j>=1)
						{
							add(dp[i+1][j-1],mult(j,v));
						}
					}
				}
			}
		}
	}
	cout<<dp[n-1][0]<<'\n';
}

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