제출 #316508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316508		nouvo25	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	64 ms	17912 KiB

skyscraper

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

const int MOD = 1e9 + 7, MAXN = 107;

int dp[MAXN][MAXN][1007][4] = {}, n, l, a[MAXN];

void add(int &a, const int &b)
{
	a += b;
	if (a >= MOD) a -= MOD;
}

int main()
{
//	freopen("test.INP","r",	stdin);
//	freopen("BAILAM.OUT","w",stdout);
	io;
	cin >> n >> l;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + 1 + n);
	
	if (n == 1)
	{
		cout << 1;
		return 0;
	}
	
	a[n + 1] = 10000;
	if (a[2] - a[1] <= l) dp[2][1][a[2] - a[1]][1] = 2;//dat o a[1] o mot dau
	if (n > 2 && 2*(a[2] - a[1]) <= l) dp[2][1][2*(a[2] - a[1])][0] = 1;//dat a[1] o giua
	for (int i = 2; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			for (int k = 0; k <= l; ++k)
				for (int z = 0; z < 3; ++z)
					if (dp[i][j][k][z])
					{
						int diff = a[i + 1] - a[i], cur = dp[i][j][k][z];
						int nwk = k + (2*j - z - 1)*diff;
						//dat endpoint
						if (z < 2)
						{
							//noi vao mot tplt
							if (nwk <= l) 
							{
								if (i == n)
								{
									//diem cuoi co the noi 2 endpoints
									add(dp[i + 1][j][nwk][z + 1], 1LL*cur*(2 - z)*j % MOD);
								}else
								{
									//khong noi duoc 2 endpoints
									add(dp[i + 1][j][nwk][z + 1], 1LL*cur*(2 - z)*(j - z) % MOD);
								}
							}
							//tao tplt moi
							nwk = k + (2*j - z + 1)*diff;
							if (nwk <= l) add(dp[i + 1][j + 1][nwk][z + 1], (2 - z)*cur % MOD);
						}
						//khong dat endpoint
						//tao tplt moi
						nwk = k + (2*j - z + 2)*diff;
						if (nwk <= l) add(dp[i + 1][j + 1][nwk][z], cur);
						//noi vao 1 tplt
						nwk = k + (2*j - z)*diff;
						if (nwk <= l) add(dp[i + 1][j][nwk][z], 1LL*(2*j - z)*cur % MOD);
						
						//noi 2 tplt
						nwk = k + (2*j - z - 2)*diff;
						if (nwk <= l && j > 1 && ((i == n) || (z < 2) || (j > 2)))
						{
							if (z == 0)
							{
								add(dp[i + 1][j - 1][nwk][z], 1LL*j*(j - 1)*cur % MOD);
							}
							if (z == 1)
							{
//								if (i == 3 && j == 1 && k == 2 && z == 1) cout << 2*j - z - 2 << '\n';
								add(dp[i + 1][j - 1][nwk][z], 1LL*(j - 1)*(j - 1)*cur % MOD);
							}
							if (z == 2)
							{
								if (i == n)
								{
									add(dp[i + 1][j - 1][nwk][z], cur);
								}else
								{
									add(dp[i + 1][j - 1][nwk][z], 1LL*(j - 2)*(j - 1)*cur % MOD);
								}
							}
						}
					}
	
	int res = 0;
	for (int i = 0; i <= l; ++i) add(res, dp[n + 1][1][i][2]);
	cout << res;
	return 0;
}

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