Submission #560664

#TimeUsernameProblemLanguageResultExecution timeMemory
560664MohamedAhmed04Skyscraper (JOI16_skyscraper)C++14
100 / 100
248 ms190572 KiB
#include <bits/stdc++.h>

using namespace std ;

const int mod = 1e9 + 7 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Sub(int x , int y)
{
	int z = x - y ;
	if(z < 0)
		z += mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (1ll * x * y) % mod ;
}

const int MAX = 100 + 10 ;

int arr[MAX] ;
int n , l ;

int dp[MAX][MAX][1004][2][2] ;

int solve(int idx , int cnt , int sum , bool t1 , bool t2)
{
	if(idx > 0 && idx < n)
		sum += (2*cnt - t1 - t2) * (arr[idx] - arr[idx-1]) ;
	if(sum > l)
		return 0 ;
	if(idx == n)
		return (cnt == 1 && t1 && t2) ;
	int &ret = dp[idx][cnt][sum][t1][t2] ;
	if(ret != -1)
		return ret ;
	ret = 0 ;
	ret = Add(ret , Mul(solve(idx+1 , cnt+1 , sum , t1 , t2) , cnt+1-t1-t2)) ;
	if(!t1)
		ret = Add(ret , solve(idx+1 , cnt+1 , sum , 1 , t2)) ;
	if(!t2)
		ret = Add(ret , solve(idx+1 , cnt+1 , sum , t1 , 1)) ;
	if(cnt >= 2)
		ret = Add(ret , Mul(solve(idx+1 , cnt-1 , sum , t1 , t2) , cnt-1)) ;
	if(cnt)
	{
		ret = Add(ret , Mul(solve(idx+1 , cnt , sum , t1 , t2) , 2 * cnt - t1 - t2)) ;
		if(!t1)
			ret = Add(ret , solve(idx+1 , cnt , sum , 1 , t2)) ;
		if(!t2)
			ret = Add(ret , solve(idx+1 , cnt , sum , t1 , 1)) ;
	}
	return ret ;
}

int main()
{
	memset(dp , -1 , sizeof(dp)) ;
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>l ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	sort(arr , arr + n) ;
	if(n == 1)
		return cout<<1<<"\n" , 0 ;
	return cout<<solve(0 , 0 , 0 , 0 , 0)<<"\n" , 0 ;
}		
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...