Submission #601708

#	Time	Username	Problem	Language	Result	Execution time	Memory
601708		1bin	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	319 ms	190528 KiB

skyscraper

#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 ;
}	

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