Submission #876825

#TimeUsernameProblemLanguageResultExecution timeMemory
876825AndrijaMSkyscraper (JOI16_skyscraper)C++14
0 / 100
73 ms524288 KiB
#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[20]; long long dp[20][(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]; } if(n<=8) { vector<int>v; for(int i=0;i<n;i++) { v.push_back(x[i]); } int ans=0; do { int kol=0; for(int i=1;i<v.size();i++) { kol+=abs(v[i]-v[i-1]); } 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 (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...