oj.uz

Submission #862615

# Submission time Handle Problem Language Result Execution time Memory
862615 2023-10-18T16:06:43 Z TAhmed33 Magneti (COCI21_magneti) C++
10 / 110
 72 ms 121452 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);
		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 4956 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 27 ms 60040 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 29 ms 60040 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 28 ms 59996 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 60048 KB Output is correct
2 Correct 27 ms 59984 KB Output is correct
3 Correct 63 ms 60096 KB Output is correct
4 Correct 31 ms 59988 KB Output is correct
5 Runtime error 72 ms 121452 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 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 4956 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 27 ms 60040 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 29 ms 60040 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 28 ms 59996 KB Output is correct
11 Correct 66 ms 60048 KB Output is correct
12 Correct 27 ms 59984 KB Output is correct
13 Correct 63 ms 60096 KB Output is correct
14 Correct 31 ms 59988 KB Output is correct
15 Runtime error 72 ms 121452 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -