Submission #28149

#	Time	Username	Problem	Language	Result	Execution time	Memory
28149		RayaBurong25_1	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	219 ms	260808 KiB

skyscraper

//cr zscoder
#include <stdio.h>
#include <algorithm>
#define MOD 1000000007
int A[105];
long long DP[105][105][1005][3];
//i: position of interest
//j: number of connected components
//k: sum of difference in heights
//l: ends filled (0, 1, 2)
//Assume: The unfilled positions for each i is A[i]
int main()
{
	int N, L;
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d %d", &N, &L);
	if (N == 1)
	{
		printf("1");
		return 0;
	}
	int i, j, k, l;
	int nk;
	long long f, g;
	for (i = 1; i <= N; i++)
		scanf("%d", &A[i]);
	std::sort(&A[1], &A[N + 1]);
	DP[1][1][0][0] = 1;
	DP[1][1][0][1] = 2;
	for (i = 1; i < N; i++)
	{
		for (j = 1; j <= i; j++)
		{
			for (k = 0; k <= L; k++)
			{
				for (l = 0; l <= 2; l++)
				{
					// printf("%d %d %d %d : %lld\n", i, j, k, l, DP[i][j][k][l]);
					nk = k + (A[i + 1] - A[i])*(2*j - l);
					if (nk > L)
						continue;
					//new component at one end
					if (i + 1 < N)
					{
						if (l < 2)
						{
							f = 2 - l;
							DP[i + 1][j + 1][nk][l + 1] = (DP[i + 1][j + 1][nk][l + 1] + DP[i][j][k][l]*f)%MOD;
						}
						//new component at other places
						DP[i + 1][j + 1][nk][l] = (DP[i + 1][j + 1][nk][l] + DP[i][j][k][l])%MOD;
					}
					//(i + 1)-[end component] or [end component]-(i + 1)
					//becomes whole sequence
					if (i + 1 == N && l == 1)
					{
						DP[i + 1][j][nk][l + 1] = (DP[i + 1][j][nk][l] + DP[i][j][k][l])%MOD;
					}
					//doesn't become whole sequence
					if (i + 1 < N && l >= 1)
					{
						f = l;
						DP[i + 1][j][nk][l] = (DP[i + 1][j][nk][l] + DP[i][j][k][l]*f)%MOD;
					}
					//(i + 1)-[free component] or [free component]-(i + 1)
					//becomes new end
					if (i + 1 < N && l < 2)
					{
						f = (j - l)*(2 - l);
						DP[i + 1][j][nk][l + 1] = (DP[i + 1][j][nk][l + 1] + DP[i][j][k][l]*f)%MOD;
					}
					//doesn't become new end
					if (i + 1 < N)
					{
						f = (j - l)*2;
						DP[i + 1][j][nk][l] = (DP[i + 1][j][nk][l] + DP[i][j][k][l]*f)%MOD;
					}
					//[end component]-(i + 1)-[end component]
					if (i + 1 == N && l == 2)
					{
						DP[i + 1][j - 1][nk][l] = (DP[i + 1][j - 1][nk][l] + DP[i][j][k][l])%MOD;
					}
					//[end component]-(i + 1)-[free component] or [free component]-(i + 1)-[end component]
					if (i + 1 < N && l >= 1)
					{
						f = l*(j - l);
						DP[i + 1][j - 1][nk][l] = (DP[i + 1][j - 1][nk][l] + DP[i][j][k][l]*f)%MOD;
					}
					//[free component]-(i + 1)-[free component]
					if (i + 1 < N && j - l > 1)
					{
						f = (j - l)*(j - l - 1);
						DP[i + 1][j - 1][nk][l] = (DP[i + 1][j - 1][nk][l] + DP[i][j][k][l]*f)%MOD;
					}
				}
			}
		}
	}
	long long Ans = 0;
	for (i = 0; i <= L; i++)
		Ans = (Ans + DP[N][1][i][2])%MOD;
	printf("%lld", Ans);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:15: warning: unused variable 'g' [-Wunused-variable]
  long long f, g;
               ^
skyscraper.cpp:17:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &L);
                        ^
skyscraper.cpp:27:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
                     ^

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