Submission #1300343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300343		tte0	Magneti (COCI21_magneti)	C++20	0 / 110	746 ms	392092 KiB

Main

// Author: Teoman Ata Korkmaz
#pragma GCC optimize("O3,unroll-loops,inline")
#include <bits/stdc++.h> 
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt")
#define int int_fast64_t
using namespace std;
constexpr int N=1e4+4;
constexpr int MOD=1e9+7;
///////////////////////////////////////////////////////////
int n,l,fact[N];
int32_t dp[N][N];//partition K (i) into N (j)
vector<int> v;

signed main(void){
    fact[0]=1;for(int i=1;i<N;i++)fact[i]=(fact[i-1]*i)%MOD;
    for(int n=0;n<N;n++)dp[0][n]=1;
    for(size_t k=1;k<N;k++){
        static size_t n;
        for(n=1;n<=k;n++){
            dp[k][n]=(dp[k][n-1]+dp[k-n][n-1])%MOD;
        }
        for(;n<=N;n++){
            dp[k][n]=dp[k][n-1];
        }
    }

    cin>>n>>l;  
    if(n==1){
        cout<<l<<endl;
        exit(0);
    }
    v.resize(n);
    for(auto& i:v){cin>>i;i--;}

    int range_size=0;
    for(int i=0;i<n;i++)range_size+=2*v[i]+1;
    
    int ans=0;
    for(int start=0;start<n;start++){
        for(int stop=0;stop<n;stop++){
            if(start==stop)continue;
            int step=l-(range_size-v[start]-v[stop]);
            //cerr<<"start stop step: "<<start<<" "<<stop<<" "<<step<<endl;
            if(step<0)continue;
            //cerr<<"yippe"<<endl;
            ans+=dp[step][n];//*fact[n-2];
            ans%=MOD;
        }
    }
    ans%=MOD;
    ans*=fact[n-2];
    ans%=MOD;

    cout<<ans<<endl;
}

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