Submission #706531

#	Time	Username	Problem	Language	Result	Execution time	Memory
706531		Username4132	Magneti (COCI21_magneti)	C++14	110 / 110	129 ms	96472 KiB

Main

#include<iostream>
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
using ll = long long;

const int MAXN=10010, MOD=1e9+7;
int n, l, arr[53], dp[52][52][MAXN], ans;

ll ex(ll b, int e){
    int ret=1;
    while(e){
        if(e&1) ret = (ret*b)%MOD;
        b = (b*b)%MOD;
        e>>=1;
    }
    return ret;
}

inline int inv(int x){
    return ex(x, MOD-2);
}

int main(){
    scanf("%d %d", &n, &l);
    forn(i, n) scanf("%d", &arr[i]);
    sort(arr, arr+n);

    dp[0][0][0]=1;
    forn(i, n-1) forn(j, n) forn(sum, l+1){
        dp[i+1][j][sum] = (((ll) j+1)*(j>0? dp[i][j-1][sum] : 0) +
        2*((ll) j+1)*(sum>=arr[i+1]? dp[i][j][sum-arr[i+1]] : 0) +
        ((ll)j+1)*(sum>=2*arr[i+1]? dp[i][j+1][sum-2*arr[i+1]] : 0))%MOD;
    }
    ll comb=1;
    forn(i, l){
        ans = (ans + dp[n-1][0][l-1-i]*comb)%MOD;
        comb = (comb*(n+i+1))%MOD;
        comb = (comb*inv(i+1))%MOD;
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d", &n, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:26:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     forn(i, n) scanf("%d", &arr[i]);
      |                ~~~~~^~~~~~~~~~~~~~~

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