| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 876821 | AndrijaM | Skyscraper (JOI16_skyscraper) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 150;
const long long mod = 1e9+7;
long long n,l;
long long x[20];
long long dp[20][(1<<15)][1005];
long long f(long long prev,long long mask,long long mx)
{
if(mask==(1<<n)-1)
{
if(mx<=l)
{
return 1;
}
return 0;
}
if(dp[prev][mask][mx]!=-1)return dp[prev][mask][mx]%mod;
long long rez=0;
for(long long bit=0;bit<n;bit++)
{
if(mask&(1<<bit))
{
}
else
{
long long dif=abs(x[bit]-x[prev]);
long long nmask=mask;
nmask|=(1<<bit);
rez+=f(bit,nmask,mx+dif)%mod;
}
}
return dp[prev][mask][mx]=rez%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>l;
memset(dp,-1,sizeof dp);
for(long long i=0;i<n;i++)
{
cin>>x[i];
}
long long ans=0;
for(long long i=0;i<n;i++)
{
long long m=0;
m|=(1<<i);
ans+=f(i,m,0)%mod;
ans%=mod;
}
cout<<ans%mod<<endl;
return 0;
}