Submission #529631

#TimeUsernameProblemLanguageResultExecution timeMemory
529631VimmerMagneti (COCI21_magneti)C++14
110 / 110
115 ms5012 KiB
#include <bits/stdc++.h> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define PB push_back #define M ll(1e9 + 7) #define sz(x) (ll)x.size() #define N 100005 #define pri(x) cout << x << endl #define endl '\n' #define all(x) (x).begin(), (x).end() #define _ << " " << using namespace std; //typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef short int si; typedef unsigned long long ull; int mlt(int x, int y) { return 1ll * x * y % M; } int sm(int x, int y) { x += y; if (x >= M) x -= M; return x; } int fact[N]; int binpow(int a, int b) { if (b == 0) return 1; int s = binpow(a, b >> 1); s = mlt(s, s); if (b & 1) s = mlt(s, a); return s; } int C(int n, int k) { return mlt(fact[n], binpow(mlt(fact[k], fact[n - k]), M - 2)); } int ans, n, l; int dp[55][10500]; int lst[55][10500]; int main() { istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("1.in", "r", stdin); fact[0] = 1; for (int i = 1; i < N; i++) fact[i] = mlt(fact[i - 1], i); cin >> n >> l; vector <int> r(n); for (int i = 0; i < n; i++) cin >> r[i]; sort(all(r)); lst[0][0] = 1; for (int i = 0; i < n; i++) { memset(dp, 0, sizeof dp); for (int j = 1; j <= i + 1; j++) for (int k = 1; k <= l; k++) { dp[j][k] = lst[j - 1][k - 1]; if (k >= r[i]) dp[j][k] = sm(dp[j][k], mlt(j + j, lst[j][k - r[i]])); if (k + 1 >= r[i] + r[i]) dp[j][k] = sm(dp[j][k], mlt(j * (j + 1), lst[j + 1][k - r[i] - r[i] + 1])); } lst[0][0] = 0; for (int j = 1; j <= i + 1; j++) for (int k = 1; k <= l; k++) { lst[j][k] = dp[j][k]; } } for (int u = 1; u <= l; u++) ans = sm(ans, mlt(C(n + l - u, n), lst[1][u])); pri(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...