Submission #852593

#	Time	Username	Problem	Language	Result	Execution time	Memory
852593		noyancanturk	Magneti (COCI21_magneti)	C++17	110 / 110	219 ms	200452 KiB

Main

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 10000
using namespace std;
const int mod=1000000007ll;

int dist[10055][55];

int sum(int a,int b){
    return ((a%mod)+(b%mod))%mod;
}
int mul(int a,int b){
    return ((a%mod)*(b%mod))%mod;
}

void solve(){
    dist[0][0]=1;
    for(int i=1;i<10055;i++){
        dist[i][0]=1;
        for(int j=1;j<55;j++){
            dist[i][j]=sum(dist[i-1][j-1],dist[i-1][j]);
        }
    }
    int n,l;
    cin>>n>>l;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int dp[n][n][l];
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<l;k++){
                dp[i][j][k]=0;
            }
        }
    }
    dp[0][0][0]=1;
    for(int i=1;i<n;i++){
        dp[i][0][0]=0;
        for(int g=0;g<=i;g++){
            for(int s=1;s<l;s++){
                //cerr<<"0 on "<<i<<" "<<g<<" "<<s<<"\n";
                if(g)dp[i][g][s]=dp[i-1][g-1][s-1];
                else dp[i][g][s]=0;
                //cerr<<dp[i][g][s]<<"\n";
                if(a[i]<=s){
                    //cerr<<"1 on "<<i<<" "<<g<<" "<<s<<"\n";
                    //cerr<<dp[i][g][s]<<" ";
                    dp[i][g][s]=sum(dp[i][g][s],mul(2*(g+1),dp[i-1][g][s-a[i]]));
                    //cerr<<dp[i][g][s]<<"\n";
                }
                if(2*a[i]-1<=s){
                    //cerr<<"2 on "<<i<<" "<<g<<" "<<s<<"\n";
                    //cerr<<dp[i][g][s]<<" ";
                    dp[i][g][s]=sum(dp[i][g][s],mul((g+2)*(g+1),dp[i-1][g+1][s-2*a[i]+1]));
                    //cerr<<dp[i][g][s]<<"\n";
                }
            }
        }
    }
    /*
    cerr<<"\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<l;k++){
                cerr<<dp[i][j][k]<<" ";
            }cerr<<"\n";
        }cerr<<"\n";
    }cerr<<"\n";
    */
    int ans=0;
    for(int i=0;i<l;i++){
        ans=sum(ans,mul(dp[n-1][0][i],dist[l-i+n-1][n]));
        //cerr<<dp[n-1][0][i]<<" "<<dist[l-i+n-1][n]<<"\n";
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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