oj.uz

Submission #1029651

# Submission time Handle Problem Language Result Execution time Memory
1029651 2024-07-21T07:05:33 Z atom Magneti (COCI21_magneti) C++17
110 / 110
 149 ms 100908 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

#define int long long
const int MOD = 1e9 + 7;
const int N = 2e4 + 5;

int bPow(int a, int b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (1LL * ans * a)  % MOD;
        a = (1LL * a * a) % MOD;
        b >>= 1;
    }
    return ans;
}

int fac[N], inv[N];

void prepare() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i)
        fac[i] = (1LL * fac[i - 1] * i) % MOD;

    inv[N - 1] = bPow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i)
        inv[i] = (1LL * inv[i + 1] * (i + 1)) % MOD;
}

int C(int k, int n) {
    if (k > n) return 0;
    return ((1LL * fac[n] * inv[n - k]) % MOD * (inv[k])) % MOD;
}

int dp[51][51][10001];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    prepare();

    int n, l;
    cin >> n >> l;
    vector <int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    sort(a.begin(), a.end());
    if (a[1] == a[n]) {
        // sub1
        int p = (n - 1) * a[1] + 1; // min length for arrangement (empty slots taken)
        ll ans = (1LL * fac[n] * C(n, n + l - p)) % MOD;      
        cout << ans << "\n";  
    }
    else {
        // dp(i, j, p): number of ways to place first i magnets into j groups, length of arrangement = p; 
        dp[0][0][0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                for (int p = 1; p <= l; ++p) {
                    // create new group;
                    dp[i][j][p] = (dp[i][j][p] + dp[i - 1][j - 1][p - 1]) % MOD;

                    // place to the end of one in j groups
                    if (p >= a[i]) {
                        int ways = 2 * j; // j groups, each groups can be placed at the begin or at the end
                        dp[i][j][p] = (dp[i][j][p] + (dp[i - 1][j][p - a[i]] * ways) % MOD) % MOD;
                    }

                    // place between two groups
                    if (p >= 2 * a[i] - 1) {
                        int ways = j * (j + 1); // from (j + 1) groups, choose two to merge into one, each pair (x, y) has two ways to place: (x__a(i)__y) or (y__a(i)__x)
                        dp[i][j][p] = (dp[i][j][p] + (dp[i - 1][j + 1][p - 2 * a[i] + 1] * ways) % MOD) % MOD;
                    }       
                }
            }
        }

        ll ans = 0;
        for (int p = 1; p <= l; ++p) {
            debug(dp[n][1][p]);
            ans += (1LL * C(n, n + l - p) * dp[n][1][p]) % MOD;
            ans %= MOD;
        }
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
Main.cpp:93:13: note: in expansion of macro 'debug'
   93 |             debug(dp[n][1][p]);
      |             ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4996 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 7 ms 4952 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 6 ms 4956 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 6 ms 4956 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 3 ms 3676 KB Output is correct
4 Correct 2 ms 2140 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 3672 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 2140 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 4996 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 7 ms 4952 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 6 ms 4956 KB Output is correct
16 Correct 2 ms 1372 KB Output is correct
17 Correct 6 ms 4956 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 3 ms 3676 KB Output is correct
22 Correct 2 ms 1884 KB Output is correct
23 Correct 3 ms 3676 KB Output is correct
24 Correct 2 ms 2140 KB Output is correct
25 Correct 3 ms 3676 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 3 ms 3672 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 2140 KB Output is correct
30 Correct 1 ms 1116 KB Output is correct
31 Correct 149 ms 100908 KB Output is correct
32 Correct 92 ms 65872 KB Output is correct
33 Correct 136 ms 100708 KB Output is correct
34 Correct 31 ms 22520 KB Output is correct
35 Correct 148 ms 100792 KB Output is correct
36 Correct 9 ms 6748 KB Output is correct
37 Correct 143 ms 100656 KB Output is correct
38 Correct 26 ms 21340 KB Output is correct
39 Correct 141 ms 100860 KB Output is correct
40 Correct 42 ms 31824 KB Output is correct
41 Correct 139 ms 100692 KB Output is correct
42 Correct 2 ms 1372 KB Output is correct
43 Correct 138 ms 100676 KB Output is correct
44 Correct 14 ms 11352 KB Output is correct
45 Correct 142 ms 100904 KB Output is correct
46 Correct 1 ms 860 KB Output is correct
47 Correct 27 ms 32028 KB Output is correct
48 Correct 12 ms 16932 KB Output is correct
49 Correct 2 ms 2652 KB Output is correct
50 Correct 1 ms 1116 KB Output is correct