oj.uz

Submission #1078538

# Submission time Handle Problem Language Result Execution time Memory
1078538 2024-08-27T19:45:36 Z Onur_Ilgaz Fishing Game (RMI19_fishing) C++17
60 / 100
 2000 ms 422416 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 200, mod = 1000000007;
vector<vector<vector<int>>> dp;

void dfs(array<int, 3> &cnt, int ind, int ways, bool red) {
	if(ind == 3) {
		if(red) {
			// cout << "to: " << cnt[0] << " " << cnt[1] << " " << cnt[2] << "\n";
			dp[cnt[0]][cnt[1]][cnt[2]] = (dp[cnt[0]][cnt[1]][cnt[2]] + ways) % mod;
		}
		return;
	}
	if(cnt[ind]) {
		--cnt[ind];
		dfs(cnt, ind + 1, ways * (cnt[ind] + 1) % mod, 1);
		++cnt[ind];
	}
	int bf = (ind + 2) % 3, bbf = (ind + 1) % 3;
	if(cnt[bf]) {
		--cnt[bf];
		++cnt[bbf];
		dfs(cnt, ind + 1, ways * (cnt[bf] + 1) % mod, red);
		++cnt[bf];
		--cnt[bbf];
	}
	if(!cnt[ind] and !cnt[bf]) {
		dfs(cnt, ind + 1, ways, red);
	}
}

void solve(int n){
	vector <set<int> > hands(3);
	for(int j = 0; j < 3; j++) {
		for(int i = 0; i < 2 * n; i++) {
			int in;
			cin >> in;
			hands[j].insert(in);
		}
	}
	vector <int> cnt(3);
	for(int j = 0; j < 3; j++) {
		for(auto it:hands[j]) {
			if(hands[(j + 1) % 3].count(it)) {
				cnt[j]++;
			}
		}
	}
	int a = cnt[0], b = cnt[1], c = cnt[2];
	vector<vector<vector<int>>> ndp(n * 3 + 1, vector<vector<int>> (n * 3 + 1, vector<int>(n * 3 + 1, 0)));
	dp = ndp;
	dp[a][b][c] = 1;
	for(int sum = n * 3; sum >= 0; sum--) for(int j = sum; j >= 0; j--) for(int k = sum - j; k >= 0; k--){
		int i = sum - j - k;
		if(i < 0) continue;
		// cout << i << " " << j << " " << k << " = " << dp[i][j][k] << "\n";
		array <int, 3> tmp = {i, j, k};
		dfs(tmp, 0, dp[i][j][k], 0);
	}
	cout << dp[0][0][0] << "\n";
}

int32_t main(){
	fast
	int t=1, n;
	cin >> n >> t;
	while(t--) solve(n);
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 996 KB Output is correct
4 Correct 23 ms 4188 KB Output is correct
5 Correct 854 ms 55968 KB Output is correct
6 Correct 1448 ms 95572 KB Output is correct
7 Execution timed out 2054 ms 150840 KB Time limit exceeded
8 Execution timed out 2059 ms 223664 KB Time limit exceeded
9 Execution timed out 2085 ms 317124 KB Time limit exceeded
10 Execution timed out 2081 ms 422416 KB Time limit exceeded