Submission #876832

#	Time	Username	Problem	Language	Result	Execution time	Memory
876832		AndrijaM	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	516 ms	410008 KiB

skyscraper

#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[105];
long long dp[15][(1<<14)][105];

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);
            if(mx+dif<=l)
            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];
    }
    if(n<=8)
    {
        sort(x,x+n);
        vector<long long>v;
        for(long long i=0;i<n;i++)
        {
            v.push_back(x[i]);
        }
        long long ans=0;
        do
        {
            long long kol=0LL;
            for(long long i=1LL;i<v.size();i++)
            {
                kol+=abs(v[i]-v[i-1LL]);
            }
            if(kol<=l)
            {
                ans++;
            }
        }while(next_permutation(v.begin(),v.end()));
        cout<<ans<<endl;
        return 0;
    }
    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;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:62:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(long long i=1LL;i<v.size();i++)
      |                                 ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80