oj.uz

Submission #519154

# Submission time Handle Problem Language Result Execution time Memory
519154 2022-01-25T18:43:46 Z Mukul202 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 99 ms 130500 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 105, mod = 1e9 + 7;

int n, k, a[N], dp[N][N][1005][3];
int yo(int i, int c, int sum, int ends) { //(id, components, sum, borders)
  if (ends > 2 || sum > k)return 0;
  if (c == 0 && i > 1) return 0;
  if (i == n + 1) return ends == 2 && c == 1;
  int &ret = dp[i][c][sum][ends];
  if (ret != -1) return ret;
  int nsum = sum + (a[i] - a[i - 1]) * (2 * c - ends);
  long long ans = 0;
  if (c >= 2) ans += 1LL * (c - 1) * yo(i + 1, c - 1, nsum, ends);  //merge two components
  if (c >= 1) ans += 1LL * (2 * c - ends) * yo(i + 1, c, nsum, ends);  //add to a component's end
  ans += 1LL * (c + 1 - ends) * yo(i + 1, c + 1, nsum, ends);  //create a new component
  if (ends < 2) ans += 1LL * (2 - ends) * yo(i + 1, c + 1, nsum, ends + 1);  //create a new end
  if (ends < 2) ans += 1LL * (2 - ends) * yo(i + 1, c, nsum, ends + 1);  //extend a component to make it a border
  ans %= mod;
  return ret = ans;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + n + 1);
  if (n == 1) return cout << 1 << '\n', 0;
  memset(dp, -1, sizeof dp);
  cout << yo(1, 0, 0, 0) << '\n';
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 48 ms 130344 KB Output is correct
3 Correct 47 ms 130356 KB Output is correct
4 Correct 53 ms 130364 KB Output is correct
5 Correct 53 ms 130320 KB Output is correct
6 Correct 47 ms 130364 KB Output is correct
7 Correct 53 ms 130384 KB Output is correct
8 Correct 49 ms 130316 KB Output is correct
9 Correct 48 ms 130304 KB Output is correct
10 Correct 55 ms 130372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 130316 KB Output is correct
2 Correct 51 ms 130328 KB Output is correct
3 Correct 51 ms 130372 KB Output is correct
4 Correct 50 ms 130356 KB Output is correct
5 Correct 50 ms 130392 KB Output is correct
6 Correct 47 ms 130372 KB Output is correct
7 Correct 48 ms 130372 KB Output is correct
8 Correct 49 ms 130404 KB Output is correct
9 Correct 48 ms 130336 KB Output is correct
10 Correct 50 ms 130372 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 48 ms 130344 KB Output is correct
3 Correct 47 ms 130356 KB Output is correct
4 Correct 53 ms 130364 KB Output is correct
5 Correct 53 ms 130320 KB Output is correct
6 Correct 47 ms 130364 KB Output is correct
7 Correct 53 ms 130384 KB Output is correct
8 Correct 49 ms 130316 KB Output is correct
9 Correct 48 ms 130304 KB Output is correct
10 Correct 55 ms 130372 KB Output is correct
11 Correct 48 ms 130316 KB Output is correct
12 Correct 51 ms 130328 KB Output is correct
13 Correct 51 ms 130372 KB Output is correct
14 Correct 50 ms 130356 KB Output is correct
15 Correct 50 ms 130392 KB Output is correct
16 Correct 47 ms 130372 KB Output is correct
17 Correct 48 ms 130372 KB Output is correct
18 Correct 49 ms 130404 KB Output is correct
19 Correct 48 ms 130336 KB Output is correct
20 Correct 50 ms 130372 KB Output is correct
21 Correct 46 ms 130292 KB Output is correct
22 Correct 99 ms 130396 KB Output is correct
23 Correct 82 ms 130372 KB Output is correct
24 Correct 78 ms 130360 KB Output is correct
25 Correct 76 ms 130280 KB Output is correct
26 Correct 73 ms 130368 KB Output is correct
27 Correct 61 ms 130432 KB Output is correct
28 Correct 71 ms 130352 KB Output is correct
29 Correct 88 ms 130500 KB Output is correct
30 Correct 79 ms 130400 KB Output is correct