Submission #1200223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200223		brover29	Magneti (COCI21_magneti)	C++17	0 / 110	285 ms	436072 KiB

Main

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1e4+29;
const ll mod=1e9+7;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,l,r[N],dp[2][N][55],c[N+100][N+100];

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

    cin>>n>>l;
    for(ll i=1;i<=n;i++){
        cin>>r[i];
    }
    c[0][0]=1;
    for(ll i=1;i<=n+l;i++){
        c[i][0]=1;
        for(ll j=1;j<=i;j++){
            c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][j]%=mod;
        }
    }
    dp[0][0][0]=1;
    ll x=0;
    for(ll i=1;i<=n;i++){
        x^=1;
        dp[x][0][0]=0;
        ll R=r[i];
        for(ll j=1;j<=i;j++){
            for(ll k=1;k<=l;k++){
                dp[x][j][k]=dp[!x][j-1][k-1];
                if(k>=R)dp[x][j][k]+=(dp[!x][j][k-R]*1ll*2*j)%mod;
                dp[x][j][k]%=mod;
                if(k>=2*R-1)dp[x][j][k]+=(dp[!x][j+1][k-2*R+1]*1ll*j*(j+1))%mod;
                dp[x][j][k]%=mod;
            }
        }
    }
    ll ans=0;
    for(ll d=1;d<=l;d++){
        ans+=(dp[x][1][d]*1ll*c[l-d+n][n])%mod;
        ans%=mod;
    }cout<<ans;
}

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