oj.uz

Submission #560663

# Submission time Handle Problem Language Result Execution time Memory
560663 2022-05-11T19:49:05 Z MohamedAhmed04 Skyscraper (JOI16_skyscraper) C++14
15 / 100
 83 ms 190544 KB 
#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<<0<<"\n" , 0 ;
	return cout<<solve(0 , 0 , 0 , 0 , 0)<<"\n" , 0 ;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 190492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 190388 KB Output is correct
2 Correct 74 ms 190544 KB Output is correct
3 Correct 73 ms 190428 KB Output is correct
4 Correct 71 ms 190476 KB Output is correct
5 Correct 72 ms 190492 KB Output is correct
6 Correct 73 ms 190532 KB Output is correct
7 Correct 72 ms 190384 KB Output is correct
8 Correct 74 ms 190408 KB Output is correct
9 Correct 83 ms 190372 KB Output is correct
10 Correct 71 ms 190436 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 190492 KB Output isn't correct
2 Halted 0 ms 0 KB -