Submission #725071

#	Time	Username	Problem	Language	Result	Execution time	Memory
725071		TheSahib	Magneti (COCI21_magneti)	C++17	110 / 110	455 ms	289396 KiB

Main

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
#define ll long long
#define pii pair<int, int>
 
using namespace std;

const int MOD = 1e9 + 7;

const int MAX = 1e4 + 100;

int comb[MAX][MAX];
int dp[55][55][MAX];
int arr[55];

void preCalc(){
    comb[0][0] = 1;
    for (int i = 1; i < MAX; i++)
    {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            comb[i][j] = ((comb[i][j] + comb[i - 1][j]) % MOD + comb[i - 1][j - 1]) % MOD;
        }
    }
}

int main(){
    preCalc();
    int n, l; cin >> n >> l;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i + 1];
    }
    sort(arr + 1, arr + n + 1);
    
    dp[0][0][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        int r = arr[i];
        for (int j = 1; j <= i; j++)
        {
            for (int d = 1; d <= l; d++)
            {
                dp[i][j][d] += (1ll * dp[i - 1][j - 1][d] * j) % MOD;
                if(r <= d){
                    dp[i][j][d] += 1ll * dp[i - 1][j][d - r] * (2 * j) % MOD;
                }
                dp[i][j][d] %= MOD;
                if(2 * r <= d){
                    dp[i][j][d] += (1ll * dp[i - 1][j + 1][d - 2 * r] * j) % MOD;
                }
                dp[i][j][d] %= MOD;
            }
        }
    }
    int ans = 0;
    for (int d = 1; d <= l; d++)
    {
        ans += 1ll * dp[n][1][d] * comb[l - d + n][n] % MOD;
        ans %= MOD;
    }
    cout << ans << '\n';
}

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