Submission #1278638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278638		vuquangsang	Magneti (COCI21_magneti)	C++20	0 / 110	138 ms	109744 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define     FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define     FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define     el "\n"
const int N = 2e4 + 2;
const int sm = 1e9 + 7;

int n, L, r[N];
long long dp[55][55][N];

void add(ll &x, ll y)
{
    x += y;
    if(x >= sm) x -= sm;
}

ll fac[N], inv_fac[N];

ll Pow(int a, int n)
{
    if(!n) return 1;
    ll res = Pow(a, n / 2);
    res = 1LL * res * res % sm;
    if(n & 1) res = 1LL * res * a % sm;
    return res;
}
void prepare()
{
    int lim = n + L;
    fac[0] = inv_fac[0] = 1;
    FOR(i, 1, lim) fac[i] = 1LL * fac[i - 1] * i % sm;
    inv_fac[lim] = Pow(fac[lim], sm - 2);
    FORD(i, lim - 1, 1) inv_fac[i] = 1LL * inv_fac[i + 1] * (i + 1) % sm;
}
ll C(int k, int n)
{
    if(k > n || k < 0) return 0;
    return 1LL * fac[n] * inv_fac[k] % sm * inv_fac[n - k] % sm;
}
void solve()
{
    cin >> n >> L;
    for(int i = 1; i <= n; i++) cin >> r[i];

    sort(r + 1, r + n + 1);

    dp[1][1][1] = 1;
    for(int i = 1; i < n; i++) for(int j = 1; j <= i; j++) {
        for(int d = 1; d <= L; d++) {
            if(d + 1 <= L) add(dp[i + 1][j + 1][d + 1], 1LL * dp[i][j][d] * (j + 1));
            if(d + r[i + 1] <= L) add(dp[i + 1][j][d + r[i + 1]], 1LL * dp[i][j][d] * 2 % sm * j % sm);
            if(d + 2 * r[i + 1] - 1 <= L) add(dp[i + 1][j - 1][d + 2 * r[i + 1] - 1], dp[i][j][d] * (j - 1) % sm);
        }
    }

    prepare();

    ll ans = 0;
    FOR(d, 1, L) {
        add(ans, 1LL * dp[n][1][d] * C(n, n + L - d));
    }
    cout << ans;
}

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define TASK "magneti"
    if(fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    solve();

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

Main.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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