Submission #316414

#	Time	Username	Problem	Language	Result	Execution time	Memory
316414		vipghn2003	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	526 ms	363000 KiB

skyscraper

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=105;
const int mod=1e9+7;

int n,L,a[N],b[N];
int dp[N][N][2][2][N*10];

int calc(int i,int cnt,bool haveL,bool haveR,int val)
{
   if(i) val+=a[i]*(2*cnt-haveL-haveR);
   if(val>L) return 0;
   int &res=dp[i][cnt][haveL][haveR][val];
   if(res!=-1) return res;
   if(i==n)
   {
      if(val>L||cnt!=1||!haveL||!haveR) return 0;
      return 1;
   }
   res=0;
   ///new comp
   res+=calc(i+1,cnt+1,haveL,haveR,val)*(cnt+1-haveL-haveR);
   ///new L
   if(!haveL) res+=calc(i+1,cnt+1,1,haveR,val);
   ///new R
   if(!haveR) res+=calc(i+1,cnt+1,haveL,1,val);
   if(cnt)
   {
       ///merge
       if(cnt>=2) res+=calc(i+1,cnt-1,haveL,haveR,val)*(cnt-1);
       ///push front
       res+=calc(i+1,cnt,haveL,haveR,val)*(cnt-haveL);
       ///push back
       res+=calc(i+1,cnt,haveL,haveR,val)*(cnt-haveR);
       ///made L
       if(!haveL) res+=calc(i+1,cnt,1,haveR,val);
       ///made R
       if(!haveR) res+=calc(i+1,cnt,haveL,1,val);
   }
   //cout<<i<<' '<<cnt<<' '<<haveL<<' '<<haveR<<' '<<val<<'\n' ;
   return res%mod;
}

main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   memset(dp,-1,sizeof dp);
   cin>>n>>L;
   if(n==1) return cout<<1,0;
   for(int i=1;i<=n;i++) cin>>b[i];
   sort(b+1,b+n+1);
   for(int i=0;i<n;i++) a[i]=b[i+1]-b[i];
   cout<<calc(0,0,0,0,0);
}

Compilation message (stderr)

skyscraper.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main()
      |      ^

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