oj.uz

Submission #862614

# Submission time Handle Problem Language Result Execution time Memory
862614 2023-10-18T16:05:06 Z TAhmed33 Magneti (COCI21_magneti) C++
10 / 110
 52 ms 42332 KB 
#include <bits/stdc++.h>
using namespace std;
int n, l, x;
int dp1[51][10001];
const int MOD = 1e9 + 7;
int nCr[10500][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 < 10500; 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 4700 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 10 ms 21120 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 10 ms 21084 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 10 ms 21116 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 21084 KB Output is correct
2 Correct 9 ms 21084 KB Output is correct
3 Correct 52 ms 21128 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Runtime error 26 ms 42332 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 4188 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 1 ms 4188 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 10 ms 21120 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 10 ms 21084 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 10 ms 21116 KB Output is correct
11 Correct 46 ms 21084 KB Output is correct
12 Correct 9 ms 21084 KB Output is correct
13 Correct 52 ms 21128 KB Output is correct
14 Correct 10 ms 21084 KB Output is correct
15 Runtime error 26 ms 42332 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -