oj.uz

답안 #1063348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063348 2024-08-17T17:05:33 Z elotelo966 Fishing Game (RMI19_fishing) C++17
100 / 100
 651 ms 405332 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 405052 KB Output is correct
2 Correct 235 ms 404820 KB Output is correct
3 Correct 240 ms 404820 KB Output is correct
4 Correct 240 ms 404988 KB Output is correct
5 Correct 360 ms 405076 KB Output is correct
6 Correct 404 ms 404884 KB Output is correct
7 Correct 432 ms 405068 KB Output is correct
8 Correct 492 ms 405080 KB Output is correct
9 Correct 566 ms 405332 KB Output is correct
10 Correct 651 ms 405076 KB Output is correct