Submission #332633

#	Time	Username	Problem	Language	Result	Execution time	Memory
332633		daniel920712	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	1199 ms	251500 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 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))
        {
            //printf("%lld %lld %lld\n",i,y,abs(all[i]-all[y]));
            DP[x][y][z]+=F(x-(1<<i),i,z+(long long) abs(all[i]-all[y]));
            DP[x][y][z]%=MOD;
        }
    }
    //printf("%lld %lld %lld %lld\n",x,y,z,DP[x][y][z]);
    return DP[x][y][z];
}
int main()
{
    long long i,ans=0;
    scanf("%lld %lld",&N,&M);
    for(i=0;i<N;i++) scanf("%lld",&all[i]);
    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:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     for(i=0;i<N;i++) scanf("%lld",&all[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~

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