Submission #1210902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210902		omarrrr	Abduction 2 (JOI17_abduction2)	C++20	0 / 100	5093 ms	580 KiB

abduction2

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define mpr make_pair

const ll N=2e6 + 10 , mod=1e9 + 7, inf=1e18;

using namespace std;

ll n,m,k,q,a,b,c,x,y;
ll t[N];
string ch;
vector<bool>vis;
ll solve(ll l,ll sm,ll tot){
    if(tot==n){
        if(sm<=k){
            return 1;
        }
        return 0;
    }
    ll s=0;
    for(ll i=0;i<n;i++){
        if(!vis[i]){
            vis[i]=1;
            s+=solve(i,sm+abs(t[l]-t[i]),tot+1);
            s%=mod;
            vis[i]=0;
        }
    }
    return s%mod;

}

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

//    freopen("dining.in","r",stdin);
//    freopen("dining.out","w",stdout);




    ll T=1;
  //  cin>>T;
    while(T--){
        cin>>n>>k;
        for(ll i=0;i<n;i++){
            cin>>t[i];
        }
        vis.resize(n,false);
        ll res=0;
        for(ll i=0;i<n;i++){
            vis[i]=1;
            res+=solve(i,0,1)%mod;
            vis[i]=0;
        }

        cout<<res<<"\n";



    }


    return 0;
}

/*
1
5 5 5
361052 142746 265738 729094 191828
3 5 4 3 430370
4 4 5 2 672057
3 2 5 1 432831
4 2 5 2 889841
2 4 4 1 766183



*/

• Subtask 1: 0 / 13
• Subtask 2: 0 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56