Submission #332640

#	Time	Username	Problem	Language	Result	Execution time	Memory
332640		daniel920712	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	1345 ms	250820 KiB

skyscraper

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
bool have[16390][20][105]={0};
long long DP[16390][20][105]={0};
long long MOD=1e9+7;
long long all[20];
long long tt[20];
long long N,M;
long long F(long long x,long long y,long long z)
{
    long long i;
    //printf("%lld %lld\n",N,M);
    if(z>M) return 0;
    if(x==0) return 1;
    if(have[x][y][z]) return DP[x][y][z];
    have[x][y][z]=1;
    for(i=0;i<N;i++)
    {
        if(x&(1<<i))
        {
            DP[x][y][z]+=F(x-(1<<i),i,z+(long long) abs(all[i]-all[y]));
            DP[x][y][z]%=MOD;
        }
    }
    return DP[x][y][z];
}
int main()
{
    long long i,ans=0,x;
    scanf("%lld %lld",&N,&M);

    for(i=0;i<N;i++)
    {
        tt[i]=i;
        scanf("%lld",&all[i]);
    }
    if(N<=8)
    {
        x=0;
        do
        {
            x=0;
            for(i=1;i<N;i++) x+=abs(all[tt[i]]-all[tt[i-1]]);
            //printf("%lld\n",x);
            ans+=(x<=M);
        }while(next_permutation(tt,tt+N));
    }
    else
    {
        for(i=0;i<N;i++)
        {
            ans+=F(((1<<N)-1)-(1<<i),i,0);
            ans%=MOD;
        }
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%lld",&all[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

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