Submission #274361

#	Time	Username	Problem	Language	Result	Execution time	Memory
274361		theStaticMind	Fishing Game (RMI19_fishing)	C++14	0 / 100	1228 ms	214048 KiB

fishing

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int dp[301][301][301];

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, q;
	cin >> n >> q;

	while(q--){
		map<int, int> A;
		map<int, int> B;
		map<int, int> C;

		for(int i = 0; i < n*2; i++){
			int x;
			cin >> x;
			A[x]++;
		}
		for(int i = 0; i < n*2; i++){
			int x;
			cin >> x;
			B[x]++;
		}
		for(int i = 0; i < n*2; i++){
			int x;
			cin >> x;
			C[x]++;
		}

		for(int i = 0; i <= 300; i++){
			for(int j = 0; j <= 300; j++){
				for(int k = 0; k <= 300; k++){
					dp[i][j][k] = 0;
				}
			}
		}

		int a = 0, b = 0, c = 0;

		for(int i = 1; i <= 3*n; i++){
			if(A[i] == 1 && B[i] == 1) a++;
			if(A[i] == 1 && C[i] == 1) b++;
			if(B[i] == 1 && C[i] == 1) c++;
		}

		dp[a][b][c] = 1;

		for(int s = a + b + c; s >= 0; s--){
			for(int i = 0; i <= 300; i++){
				for(int j = 0; j <= 300 && i + j <= s; j++){
					int k = s - i - j;
/*
					dp[i-1][j][k] , i 
					dp[i-1][j][k] , i 
					dp[i-1][j][k] , i 
					dp[i-1][j][k] , i 

					dp[i][j-1][k+1], j
					dp[i][j-1][k+1], j
					dp[i][j-1][k+1], j
					dp[i][j-1][k+1], j
///////////////////////////////////////////////////////////////////////////
					dp[i-2][j+1][k] , i * (i-1) 
					dp[i-2][j+1][k] , i * (i-1)
					dp[i-1][j][k-1] , i * k
					dp[i-1][j][k-1] , i * k

					dp[i-1][j][k+1], j * i
					dp[i-1][j][k+1], j * i
					dp[i][j-1][k], j * (k+1)
					dp[i][j-1][k], j * (k+1)
					///////////////////////////////////////////////////////////////////////////
				+	dp[i-2][j][k] , i * (i-1) * (j+1)
				+	dp[i-1][j+1][k-1] , i * (i-1) * k
				+	dp[i-1][j-1][k-1] , i * k * j
				+	dp[i][j][k-2] , i * k * (k-1)
				+	dp[i-1][j-1][k+1], j * i * j
				+	dp[i][j][k], j * i * (k+1)
				+	dp[i][j-2][k], j * (k+1) * (j-1)
				+	dp[i+1][j-1][k-1], j * (k+1) * k
*/
					// a-a-b
					if(i-2>=0 && j>=0 && k>=0)
					dp[i-2][j][k] = (dp[i-2][j][k] + dp[i][j][k] * i * (i - 1) * (j + 1)) % modulo;


					// a-a-c
					if(i-1>=0 && j+1<=300 && k-1>=0)
					dp[i-1][j+1][k-1] = (dp[i-1][j+1][k-1] + dp[i][j][k] * i * (i - 1) * k) % modulo;

					// a-c-b
					if(i-1>=0 && j-1>=0 && k-1>=0)
					dp[i-1][j-1][k-1] = (dp[i-1][j-1][k-1] + dp[i][j][k] * i * k * j) % modulo;

					// a-c-c
					if(i>=0 && j>=0 && k-2>=0)
					dp[i][j][k-2] = (dp[i][j][k-2] + dp[i][j][k] * i * k * (k - 1)) % modulo;

					// b-a-b
					if(i-1>=0 && j-1>=0 && k+1<=300)
					dp[i-1][j-1][k+1] = (dp[i-1][j-1][k+1] + dp[i][j][k] * j * i * j) % modulo;

					// b-a-c
					//

					// b-c-b
					if(i>=0 && j-2>=0 && k>=0)
					dp[i][j-2][k] = (dp[i][j-2][k] + dp[i][j][k] * j * (k + 1) * (j - 1)) % modulo;

					// b-c-c
					if(i+1<=300 && j-1>=0 && k-1>=0)
					dp[i+1][j-1][k-1] = (dp[i+1][j-1][k-1] + dp[i][j][k] * j * (k + 1) * k) % modulo;
				}
			}
		}

		cout << dp[0][0][0] << "\n";
	}
}

• Subtask 1: 0 / 100