제출 #1063348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063348		elotelo966	Fishing Game (RMI19_fishing)	C++17	100 / 100	651 ms	405332 KiB

fishing

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 205
#define fi first
#define se second

set<int> a,b;

int dp[3][lim][lim][lim][2];

inline int add(int x,int y){
	if(x+y>=mod)return x+y-mod;
	return x+y;
}

inline int carp(int x,int y){
	return (x%mod)*(y%mod)%mod;
}

inline int f(int kim,int ab,int bc,int ac,int tut){
	if(ab==0 && bc==0 && ac==0)return 1;
	if(~dp[kim][ab][bc][ac][tut])return dp[kim][ab][bc][ac][tut];
	int cev=0;
	if(kim==0){
		if(ab==0 && ac==0){
			cev=add(cev,f(kim+1,ab,bc,ac,0));
		}
		else{
			if(ab)cev=add(cev,carp(ab,f(kim+1,ab-1,bc,ac,1)));
			if(ac)cev=add(cev,carp(ac,f(kim+1,ab,bc+1,ac-1,0)));
		}
	}
	else if(kim==1){
		if(bc==0 && ab==0){
			cev=add(cev,f(kim+1,ab,bc,ac,tut));
		}
		else{
			if(bc)cev=add(cev,carp(bc,f(kim+1,ab,bc-1,ac,1)));
			if(ab)cev=add(cev,carp(ab,f(kim+1,ab-1,bc,ac+1,tut)));
		}
	}
	else{
		if(ac==0 && bc==0){
			if(tut)cev=add(cev,f(0,ab,bc,ac,1));
		}
		else{
			if(ac)cev=add(cev,carp(ac,f(0,ab,bc,ac-1,1)));
			if(tut && bc)cev=add(cev,carp(bc,f(0,ab+1,bc-1,ac,0)));
		}
	}
	return dp[kim][ab][bc][ac][tut]=cev;
}

int32_t main(){
	faster
	int n,t;cin>>n>>t;
	while(t--){
		memset(dp,-1,sizeof(dp));
		a.clear();
		b.clear();
		int ab=0,ac=0,bc=0;
		for(int i=1;i<=2*n;i++){
			int x;cin>>x;
			a.insert(x);
		}
		
		for(int i=1;i<=2*n;i++){
			int x;cin>>x;
			if(a.count(x))ab++;
			b.insert(x);
		}
		
		for(int i=1;i<=2*n;i++){
			int x;cin>>x;
			if(b.count(x))bc++;
			if(a.count(x))ac++;
		}
		
		cout<<f(0,ab,bc,ac,0)<<'\n';
		
	}
	return 0;
}

• Subtask 1: 100 / 100