답안 #274495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274495	2020-08-19T12:22:28 Z	theStaticMind	Fishing Game (RMI19_fishing)	C++14	80 / 100	2000 ms	107256 KB

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;

		auto go = [&](int i, int j, int k, int o, int p, int r){
			int x = i, y = j, z = k;
			int K = 1;
			if(o == -1){
				if(x != 0 || y != 0) return;
			} 
			else if(o == 0){
				if(x){
					K *= x;
					x--;
				}
				else return;
			}
			else{
				if(y){
					K *= y;
					y--;
					z++;
				}
				else return;
			}

			if(p == -1){
				if(x != 0 || z != 0) return;
			} 
			else if(p == 0){
				if(x){
					K *= x;
					x--;
					y++;
				}
				else return;
			}
			else{
				if(z){
					K *= z;
					z--;
				}
				else return;
			}

			if(r == -1){
				if(y != 0 || z != 0) return;
			} 
			else if(r == 0){
				if(y){
					K *= y;
					y--;	
				}
				else return;
			}
			else{
				if(z){
					K *= z;
					z--;
					x++;
				}
				else return;
			}

			if(x >= 0 && y >= 0 && z >= 0 && !(x == i && y == j && z == k)){
				dp[x][y][z] = (dp[x][y][z] + 1ll * K * dp[i][j][k] % modulo) % modulo;
			}

		};

		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;
			
					for(int o = -1; o <= 1; o++){
						for(int p = -1; p <= 1; p++){
							for(int r = -1; r <= 1; r++){
								go(i, j, k, o, p, r);
							}
						}
					}
					
				}
			}
		}

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

Subtask #1

80.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	107000 KB	Output is correct
2	Correct	167 ms	107000 KB	Output is correct
3	Correct	149 ms	107128 KB	Output is correct
4	Correct	156 ms	107204 KB	Output is correct
5	Correct	587 ms	107256 KB	Output is correct
6	Correct	800 ms	107232 KB	Output is correct
7	Correct	1214 ms	107176 KB	Output is correct
8	Correct	1725 ms	107228 KB	Output is correct
9	Execution timed out	2088 ms	107256 KB	Time limit exceeded
10	Execution timed out	2087 ms	107128 KB	Time limit exceeded