oj.uz

Submission #876832

# Submission time Handle Problem Language Result Execution time Memory
876832 2023-11-22T12:05:46 Z AndrijaM Skyscraper (JOI16_skyscraper) C++14
20 / 100
 516 ms 410008 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);
            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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 202332 KB Output is correct
2 Correct 23 ms 202324 KB Output is correct
3 Correct 23 ms 202280 KB Output is correct
4 Correct 24 ms 202616 KB Output is correct
5 Correct 24 ms 202328 KB Output is correct
6 Correct 24 ms 202196 KB Output is correct
7 Correct 23 ms 202332 KB Output is correct
8 Correct 24 ms 202320 KB Output is correct
9 Correct 23 ms 202328 KB Output is correct
10 Correct 27 ms 202628 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 202332 KB Output is correct
2 Correct 51 ms 202324 KB Output is correct
3 Correct 364 ms 202420 KB Output is correct
4 Correct 50 ms 202440 KB Output is correct
5 Correct 37 ms 202332 KB Output is correct
6 Correct 369 ms 202420 KB Output is correct
7 Correct 43 ms 202324 KB Output is correct
8 Correct 327 ms 202420 KB Output is correct
9 Correct 516 ms 202332 KB Output is correct
10 Correct 53 ms 202332 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 202332 KB Output is correct
2 Correct 23 ms 202324 KB Output is correct
3 Correct 23 ms 202280 KB Output is correct
4 Correct 24 ms 202616 KB Output is correct
5 Correct 24 ms 202328 KB Output is correct
6 Correct 24 ms 202196 KB Output is correct
7 Correct 23 ms 202332 KB Output is correct
8 Correct 24 ms 202320 KB Output is correct
9 Correct 23 ms 202328 KB Output is correct
10 Correct 27 ms 202628 KB Output is correct
11 Correct 66 ms 202332 KB Output is correct
12 Correct 51 ms 202324 KB Output is correct
13 Correct 364 ms 202420 KB Output is correct
14 Correct 50 ms 202440 KB Output is correct
15 Correct 37 ms 202332 KB Output is correct
16 Correct 369 ms 202420 KB Output is correct
17 Correct 43 ms 202324 KB Output is correct
18 Correct 327 ms 202420 KB Output is correct
19 Correct 516 ms 202332 KB Output is correct
20 Correct 53 ms 202332 KB Output is correct
21 Runtime error 189 ms 410008 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -