oj.uz

Submission #274082

# Submission time Handle Problem Language Result Execution time Memory
274082 2020-08-19T08:25:39 Z Fasho Fishing Game (RMI19_fishing) C++14
100 / 100
 427 ms 164032 KB 
#include <bits/stdc++.h>
#define N 301
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define mod 1000000007
using namespace std;

ll n,m,sum,t,tut1[N],tut2[N],dp[201][201][201][3][2];

ll add(ll x,ll y)
{
	x%=mod;
	y%=mod;
	return (((x+y)%mod)+mod)%mod;
}
ll carp(ll x,ll y)
{
	x%=mod;
	y%=mod;
	return (((x*y)%mod)+mod)%mod;
}

ll f(ll a,ll b,ll c,ll x,bool flag)
{

	if(dp[a][b][c][x][flag])
		return dp[a][b][c][x][flag];
	if(!a && !b && !c)
		return dp[a][b][c][x][flag]=1;
	// cerr<<a<<sp<<b<<sp<<c<<sp<<x<<endl;
	if(x==0)
	{
		ll top=0;
		if(!a && !b)
			return dp[a][b][c][x][flag]=f(a,b,c,1,flag);
		if(a)
			top=add(top,carp(f(a-1,b,c,1,1),a));
		if(b)
			top=add(top,carp(f(a,b-1,c+1,1,flag),b));
		return dp[a][b][c][x][flag]=top;
	}
	if(x==1)
	{
		ll top=0;
		if(!a && !c)
			return dp[a][b][c][x][flag]=f(a,b,c,2,flag);
		if(c)
			top=add(top,carp(f(a,b,c-1,2,1),c));
		if(a)
			top=add(top,carp(f(a-1,b+1,c,2,flag),a));
		// cout<<a<<sp<<b<<sp<<c<<sp<<top<<endl;
		return dp[a][b][c][x][flag]=top;
	}
	if(x==2)
	{
		ll top=0;
		if(!b && !c)
			return dp[a][b][c][x][flag]=f(a,b,c,0,0);
		if(b)
			top=add(top,carp(f(a,b-1,c,0,0),b));
		if(c && flag)
			top=add(top,carp(f(a+1,b,c-1,0,0),c));
		return dp[a][b][c][x][flag]=top;
	}
	return 1;

}

int main()
{
	fast;
	cin>>n>>t;
	while(t--)
	{
		ll a=0,b=0,c=0;
		fo(i,1,n*3)
			tut1[i]=0,tut2[i]=0;
		fo(i,1,3)
			fo(j,1,n*2)
				{
					ll x;
					cin>>x;
					// cout<<x<<endl;
					if(tut1[x])
					{
						tut2[x]=i;
						if(tut1[x]==i)
							continue;
						if(tut1[x]==1)
						{
							if(i==2)
								a++;
							else
								b++;
						}
						else
							c++;
					}
					else
						tut1[x]=i;
				}
		// cout<<a<<sp<<b<<sp<<c<<endl;
			cout<<f(a,b,c,0,0)<<endl;
	}

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 1416 KB Output is correct
4 Correct 6 ms 4736 KB Output is correct
5 Correct 60 ms 33400 KB Output is correct
6 Correct 90 ms 51064 KB Output is correct
7 Correct 150 ms 73488 KB Output is correct
8 Correct 241 ms 100508 KB Output is correct
9 Correct 263 ms 132132 KB Output is correct
10 Correct 427 ms 164032 KB Output is correct