oj.uz

Submission #876802

# Submission time Handle Problem Language Result Execution time Memory
876802 2023-11-22T11:06:42 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
0 / 100
 1487 ms 404420 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[maxn];
long long dp[15][(1<<15)][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];
    }
    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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 404220 KB Output is correct
2 Correct 47 ms 404188 KB Output is correct
3 Correct 48 ms 404240 KB Output is correct
4 Correct 47 ms 404324 KB Output is correct
5 Incorrect 49 ms 404304 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 404420 KB Output is correct
2 Incorrect 1487 ms 404420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 404220 KB Output is correct
2 Correct 47 ms 404188 KB Output is correct
3 Correct 48 ms 404240 KB Output is correct
4 Correct 47 ms 404324 KB Output is correct
5 Incorrect 49 ms 404304 KB Output isn't correct
6 Halted 0 ms 0 KB -