oj.uz

Submission #862616

# Submission time Handle Problem Language Result Execution time Memory
862616 2023-10-18T16:07:39 Z TAhmed33 Magneti (COCI21_magneti) C++
30 / 110
 69 ms 60108 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 27 ms 60072 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4840 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 28 ms 60032 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 27 ms 60108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 60096 KB Output is correct
2 Correct 30 ms 60064 KB Output is correct
3 Correct 69 ms 59996 KB Output is correct
4 Correct 27 ms 59996 KB Output is correct
5 Correct 62 ms 60100 KB Output is correct
6 Correct 27 ms 59988 KB Output is correct
7 Correct 58 ms 59996 KB Output is correct
8 Correct 57 ms 59984 KB Output is correct
9 Correct 27 ms 59992 KB Output is correct
10 Correct 28 ms 59988 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 27 ms 60072 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4840 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 28 ms 60032 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 27 ms 60108 KB Output is correct
11 Correct 66 ms 60096 KB Output is correct
12 Correct 30 ms 60064 KB Output is correct
13 Correct 69 ms 59996 KB Output is correct
14 Correct 27 ms 59996 KB Output is correct
15 Correct 62 ms 60100 KB Output is correct
16 Correct 27 ms 59988 KB Output is correct
17 Correct 58 ms 59996 KB Output is correct
18 Correct 57 ms 59984 KB Output is correct
19 Correct 27 ms 59992 KB Output is correct
20 Correct 28 ms 59988 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -