oj.uz

Submission #28147

# Submission time Handle Problem Language Result Execution time Memory
28147 2017-07-15T13:19:10 Z RayaBurong25_1 Skyscraper (JOI16_skyscraper) C++14
5 / 100
 0 ms 260808 KB 
//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)
						{
							DP[i + 1][j + 1][nk][l + 1] = (DP[i + 1][j + 1][nk][l + 1] + DP[i][j][k][l]*(2 - l))%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)
					{
						DP[i + 1][j][nk][l] = (DP[i + 1][j][nk][l] + DP[i][j][k][l]*l)%MOD;
					}
					//(i + 1)-[free component] or [free component]-(i + 1)
					//becomes new end
					if (i + 1 < N && l < 2)
					{
						DP[i + 1][j][nk][l + 1] = (DP[i + 1][j][nk][l + 1] + DP[i][j][k][l]*(j - l)*(2 - l))%MOD;
					}
					//doesn't become new end
					if (i + 1 < N)
					{
						DP[i + 1][j][nk][l] = (DP[i + 1][j][nk][l] + DP[i][j][k][l]*(j - l)*2)%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)
					{
						DP[i + 1][j - 1][nk][l] = (DP[i + 1][j - 1][nk][l] + DP[i][j][k][l]*l*(j - l))%MOD;
					}
					//[free component]-(i + 1)-[free component]
					if (i + 1 < N && j - l > 1)
					{
						DP[i + 1][j - 1][nk][l] = (DP[i + 1][j - 1][nk][l] + DP[i][j][k][l]*(j - l)*(j - l - 1))%MOD;
					}
				}
			}
		}
	}
	long long Ans = 0;
	for (i = 0; i <= L; i++)
		Ans += DP[N][1][i][2];
	printf("%lld", Ans);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:12: warning: unused variable 'f' [-Wunused-variable]
  long long f, g;
            ^
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 260808 KB Output is correct
2 Correct 0 ms 260808 KB Output is correct
3 Correct 0 ms 260808 KB Output is correct
4 Correct 0 ms 260808 KB Output is correct
5 Correct 0 ms 260808 KB Output is correct
6 Correct 0 ms 260808 KB Output is correct
7 Correct 0 ms 260808 KB Output is correct
8 Correct 0 ms 260808 KB Output is correct
9 Correct 0 ms 260808 KB Output is correct
10 Correct 0 ms 260808 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 260808 KB Output is correct
2 Correct 0 ms 260808 KB Output is correct
3 Correct 0 ms 260808 KB Output is correct
4 Correct 0 ms 260808 KB Output is correct
5 Correct 0 ms 260808 KB Output is correct
6 Correct 0 ms 260808 KB Output is correct
7 Correct 0 ms 260808 KB Output is correct
8 Correct 0 ms 260808 KB Output is correct
9 Incorrect 0 ms 260808 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 260808 KB Output is correct
2 Correct 0 ms 260808 KB Output is correct
3 Correct 0 ms 260808 KB Output is correct
4 Correct 0 ms 260808 KB Output is correct
5 Correct 0 ms 260808 KB Output is correct
6 Correct 0 ms 260808 KB Output is correct
7 Correct 0 ms 260808 KB Output is correct
8 Correct 0 ms 260808 KB Output is correct
9 Correct 0 ms 260808 KB Output is correct
10 Correct 0 ms 260808 KB Output is correct
11 Correct 0 ms 260808 KB Output is correct
12 Correct 0 ms 260808 KB Output is correct
13 Correct 0 ms 260808 KB Output is correct
14 Correct 0 ms 260808 KB Output is correct
15 Correct 0 ms 260808 KB Output is correct
16 Correct 0 ms 260808 KB Output is correct
17 Correct 0 ms 260808 KB Output is correct
18 Correct 0 ms 260808 KB Output is correct
19 Incorrect 0 ms 260808 KB Output isn't correct
20 Halted 0 ms 0 KB -