oj.uz

답안 #332834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332834 2020-12-03T15:59:26 Z kapsel Fishing Game (RMI19_fishing) C++17
100 / 100
 294 ms 190316 KB 
#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double

const LL MOD = 1e9 + 7;
const int N = 204;
LL dp[N][N][N][3][2];
bool good[N][N][N][3][2];

LL solve(LL a, LL b, LL c, int x, int d) {
	if(a+b+c == 0)
		return 1;
	if(x == 3) {
		if(!d)
			return 0;
		return solve(a, b, c, 0, 0);
	}
	if(good[a][b][c][x][d]) return dp[a][b][c][x][d];
	good[a][b][c][x][d] = 1;
	if(x == 0) {
		if(a+c == 0) return dp[a][b][c][x][d] = solve(a, b, c, x+1, d);
		if(a) dp[a][b][c][x][d] += (a * solve(a-1, b, c, x+1, 1))%MOD;
		if(c) dp[a][b][c][x][d] += (c * solve(a, b+1, c-1, x+1, d))%MOD;
		dp[a][b][c][x][d] %= MOD;
		return dp[a][b][c][x][d];
	}
	if(x == 1) {
		if(a+b == 0) return dp[a][b][c][x][d] = solve(a, b, c, x+1, d);
		if(b) dp[a][b][c][x][d] += (b * solve(a, b-1, c, x+1, 1))%MOD;
		if(a) dp[a][b][c][x][d] += (a * solve(a-1, b, c+1, x+1, d))%MOD;
		dp[a][b][c][x][d] %= MOD;
		return dp[a][b][c][x][d];
	}
	if(x == 2) {
		if(b+c == 0) return dp[a][b][c][x][d] = solve(a, b, c, x+1, d);
		if(c) dp[a][b][c][x][d] += (c * solve(a, b, c-1, x+1, 1))%MOD;
		if(b) dp[a][b][c][x][d] += (b * solve(a+1, b-1, c, x+1, d))%MOD;
		dp[a][b][c][x][d] %= MOD;
		return dp[a][b][c][x][d];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, t;
	cin>>n>>t;
	while(t--) {
		set<int> l[3];
		int a = 0, b = 0, c = 0;
		for(int i=0; i<3; i++) {
			for(int j=0; j<2*n; j++) {
				int r;
				cin>>r;
				l[i].insert(r);
			}
		}
		for(int i=1; i<=(3*n); i++) {
			if(l[0].count(i) && l[1].count(i))
				a++;
			if(l[1].count(i) && l[2].count(i))
				b++;
			if(l[2].count(i) && l[0].count(i))
				c++;
		}
		cout<<solve(a, b, c, 0, 0)<<"\n";
	}
}

Compilation message

fishing.cpp: In function 'long long int solve(long long int, long long int, long long int, int, int)':
fishing.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 1900 KB Output is correct
4 Correct 4 ms 6124 KB Output is correct
5 Correct 39 ms 40300 KB Output is correct
6 Correct 69 ms 60780 KB Output is correct
7 Correct 103 ms 86508 KB Output is correct
8 Correct 152 ms 117740 KB Output is correct
9 Correct 219 ms 153708 KB Output is correct
10 Correct 294 ms 190316 KB Output is correct