Submission #862616

#	Time	Username	Problem	Language	Result	Execution time	Memory
862616		TAhmed33	Magneti (COCI21_magneti)	C++98	30 / 110	69 ms	60108 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, l, x;
int dp1[51][10001];
const int MOD = 1e9 + 7;
int nCr[30500][500];
int ans1 (int pos, int cur) {
	if (pos == n) return 1;
	if (cur >= l) return 0;
	if (dp1[pos][cur] != -1) return dp1[pos][cur];
	return dp1[pos][cur] = (ans1(pos + 1, cur + x) + ans1(pos, cur + 1)) % (MOD);
}
int main () {
	cin >> n >> l;
	if (n > 10) {
		cin >> x;
		memset(dp1, -1, sizeof(dp1));
		int fact = 1;
		for (int i = 1; i <= n; i++) fact = (fact * 1ll * i) % MOD;
		cout << (fact * 1ll * ans1(0, 0)) % MOD << '\n';
		return 0;
	}	
	for (int i = 0; i < 30500; i++) {
		for (int j = 0; j <= min(499, i); j++) {
			if (j == 0 || j == i) {
				nCr[i][j] = 1;
			} else {
				nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % MOD;
			}
		}
	}
	vector <pair <int, int>> arr(n);
	for (int i = 0; i < n; i++) {
		int x; cin >> x; arr[i] = {x, i};
	}
	sort(arr.begin(), arr.end());
	int sum = 0;
	do {
		int length = 1;
		for (int i = 1; i < n; i++) length += max(arr[i].first, arr[i - 1].first);
		if (l - length + n < 0) continue;
		sum = (sum + nCr[l - length + n][n]) % MOD;
	} while (next_permutation(arr.begin(), arr.end()));
	cout << sum << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50