oj.uz

Submission #360125

# Submission time Handle Problem Language Result Execution time Memory
360125 2021-01-27T13:31:36 Z LucaDantas Skyscraper (JOI16_skyscraper) C++17
100 / 100
 164 ms 47468 KB 
#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 105, maxl = 1005, mod = 1000000007;

int dp[maxn][maxn][maxl][3];

// dp(i, j, k, z) | i == current position | j == number of components
// k == value of the perm | z == number of ends filled

void add(int& a, long long b) {
	b %= mod;
	a += b;
	if(a >= mod) a -= mod;
}

int main() {
	int n, L; scanf("%d %d", &n, &L);

	vector<int> a(n);
	for(int& x : a)
		scanf("%d", &x);
	sort(a.begin(), a.end());
	
	if(n == 1) {puts("1"); return 0;}

	for(int i = 0; i <= L; i++)
		dp[0][0][i][0] = 1;

	for(int i = 0; i < n; i++) {
		int dif = a[i] - (i?a[i-1]:0);
		for(int j = 0; j <= i; j++) {
			for(int k = 0; k <= L; k++) {
				for(int z = 0; z <= min(j, 2); z++) {

					int val = k + dif * (2*j - z);

					if(val > L) continue;
					// Merge a component with one of the ends
					if(j && z != 2)
						add(dp[i+1][j][val][z+1], 1ll * dp[i][j][k][z] * (2-z));
					// Create a new component one of the ends
					if(z != 2)
						add(dp[i+1][j+1][val][z+1], 1ll * dp[i][j][k][z] * (2-z));
					// Merge two components in the middle
					if(j >= 2)
						add(dp[i+1][j-1][val][z], 1ll * dp[i][j][k][z] * (j-1));
					// Append to an existing component
					if(j)
						add(dp[i+1][j][val][z], 1ll * dp[i][j][k][z] * (2*j - z));
					// Create a new component in the middle
					add(dp[i+1][j+1][val][z], 1ll * dp[i][j][k][z] * (j+1-z));
				}
			}
		}
	}

	printf("%d\n", dp[n][1][L][2]);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:18:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  int n, L; scanf("%d %d", &n, &L);
      |            ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 1012 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 1 ms 876 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 876 KB Output is correct
19 Correct 1 ms 876 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 3 ms 3180 KB Output is correct
22 Correct 145 ms 36908 KB Output is correct
23 Correct 155 ms 43884 KB Output is correct
24 Correct 152 ms 47084 KB Output is correct
25 Correct 162 ms 43884 KB Output is correct
26 Correct 143 ms 43372 KB Output is correct
27 Correct 74 ms 31616 KB Output is correct
28 Correct 89 ms 34944 KB Output is correct
29 Correct 143 ms 47468 KB Output is correct
30 Correct 164 ms 43756 KB Output is correct