oj.uz

Submission #876831

# Submission time Handle Problem Language Result Execution time Memory
876831 2023-11-22T12:03:53 Z AndrijaM Skyscraper (JOI16_skyscraper) C++14
5 / 100
 1515 ms 202580 KB 
#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);
            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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:61: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]
   61 |             for(long long i=1LL;i<v.size();i++)
      |                                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 202368 KB Output is correct
2 Correct 26 ms 202324 KB Output is correct
3 Correct 24 ms 202320 KB Output is correct
4 Correct 25 ms 202332 KB Output is correct
5 Correct 25 ms 202332 KB Output is correct
6 Correct 25 ms 202576 KB Output is correct
7 Correct 24 ms 202260 KB Output is correct
8 Correct 24 ms 202328 KB Output is correct
9 Correct 27 ms 202452 KB Output is correct
10 Correct 24 ms 202236 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 202332 KB Output is correct
2 Incorrect 1515 ms 202580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 202368 KB Output is correct
2 Correct 26 ms 202324 KB Output is correct
3 Correct 24 ms 202320 KB Output is correct
4 Correct 25 ms 202332 KB Output is correct
5 Correct 25 ms 202332 KB Output is correct
6 Correct 25 ms 202576 KB Output is correct
7 Correct 24 ms 202260 KB Output is correct
8 Correct 24 ms 202328 KB Output is correct
9 Correct 27 ms 202452 KB Output is correct
10 Correct 24 ms 202236 KB Output is correct
11 Correct 73 ms 202332 KB Output is correct
12 Incorrect 1515 ms 202580 KB Output isn't correct
13 Halted 0 ms 0 KB -