oj.uz

Submission #876830

# Submission time Handle Problem Language Result Execution time Memory
876830 2023-11-22T12:03:27 Z AndrijaM Skyscraper (JOI16_skyscraper) C++14
5 / 100
 1 ms 500 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -