Submission #112364

#	Time	Username	Problem	Language	Result	Execution time	Memory
112364		Mahdi_Jfri	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	580 ms	69772 KiB

skyscraper

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

#define ll long long
#define pb push_back

const int maxn = 1e2 + 20;
const int maxl = 1e3 + 20;
const int mod = 1e9 + 7;

int dp[maxn][maxn][maxl][2][2] , a[maxn];

inline void mkay(int &a)
{
	if(a >= mod)
		a -= mod;
	else if(a < 0)
		a += mod;
}

void reval(int i , int j , int k , int x , int y , int val)
{
	if(k < maxl)
		mkay(dp[i][j][k][x][y] += val);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , l;
	cin >> n >> l;

	for(int i = 1; i <= n; i++)
		cin >> a[i];

	sort(a + 1 , a + n + 1);

	for(int x = 0; x < 2; x++)
		for(int y = 0; y < 2; y++)
			dp[1][1][0][x][y] = 1;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			for(int k = 0; k <= l; k++)
				for(int x = 0; x < 2; x++)
					for(int y = 0; y < 2; y++)
					{
						int dif = a[i + 1] - a[i] , val = dp[i][j][k][x][y];
						int tmp = (2 * j - 2 + x + y) * dif;

						if(x)
						{
							reval(i + 1 , j , k + tmp , 1 , y , val);
							reval(i + 1 , j , k + tmp , 0 , y , val);

							reval(i + 1 , j + 1 , k + tmp , 1 , y , val);
							reval(i + 1 , j + 1 , k + tmp , 0 , y , val);
						}
						if(y)
						{
							reval(i + 1 , j , k + tmp , x , 1 , val);
							reval(i + 1 , j , k + tmp , x , 0 , val);

							reval(i + 1 , j + 1 , k + tmp , x , 1 , val);
							reval(i + 1 , j + 1 , k + tmp , x , 0 , val);
						}

						val = 1LL * val * (j - 1) % mod;
						if(j >= 2)
							reval(i + 1 , j - 1 , k + tmp , x , y , val);

						reval(i + 1 , j , k + tmp , x , y , val * 2 % mod);
						reval(i + 1 , j + 1 , k + tmp , x , y , val);
					}

	int sum = 0;
	for(int i = 0; i <= l; i++)
		mkay(sum += dp[n][1][i][0][0]);

	cout << sum << endl;
}

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