oj.uz

Submission #971992

# Submission time Handle Problem Language Result Execution time Memory
971992 2024-04-29T16:26:18 Z Niosakaru Skyscraper (JOI16_skyscraper) C++17
100 / 100
 66 ms 130640 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 348 KB Output is correct
2 Correct 66 ms 130520 KB Output is correct
3 Correct 18 ms 130392 KB Output is correct
4 Correct 19 ms 130284 KB Output is correct
5 Correct 19 ms 130504 KB Output is correct
6 Correct 18 ms 130396 KB Output is correct
7 Correct 19 ms 130396 KB Output is correct
8 Correct 20 ms 130396 KB Output is correct
9 Correct 20 ms 130560 KB Output is correct
10 Correct 23 ms 130448 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 130392 KB Output is correct
2 Correct 19 ms 130396 KB Output is correct
3 Correct 20 ms 130376 KB Output is correct
4 Correct 20 ms 130464 KB Output is correct
5 Correct 20 ms 130400 KB Output is correct
6 Correct 22 ms 130396 KB Output is correct
7 Correct 21 ms 130396 KB Output is correct
8 Correct 21 ms 130396 KB Output is correct
9 Correct 21 ms 130364 KB Output is correct
10 Correct 21 ms 130396 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 66 ms 130520 KB Output is correct
3 Correct 18 ms 130392 KB Output is correct
4 Correct 19 ms 130284 KB Output is correct
5 Correct 19 ms 130504 KB Output is correct
6 Correct 18 ms 130396 KB Output is correct
7 Correct 19 ms 130396 KB Output is correct
8 Correct 20 ms 130396 KB Output is correct
9 Correct 20 ms 130560 KB Output is correct
10 Correct 23 ms 130448 KB Output is correct
11 Correct 21 ms 130392 KB Output is correct
12 Correct 19 ms 130396 KB Output is correct
13 Correct 20 ms 130376 KB Output is correct
14 Correct 20 ms 130464 KB Output is correct
15 Correct 20 ms 130400 KB Output is correct
16 Correct 22 ms 130396 KB Output is correct
17 Correct 21 ms 130396 KB Output is correct
18 Correct 21 ms 130396 KB Output is correct
19 Correct 21 ms 130364 KB Output is correct
20 Correct 21 ms 130396 KB Output is correct
21 Correct 19 ms 130640 KB Output is correct
22 Correct 66 ms 130552 KB Output is correct
23 Correct 45 ms 130396 KB Output is correct
24 Correct 58 ms 130356 KB Output is correct
25 Correct 48 ms 130392 KB Output is correct
26 Correct 46 ms 130544 KB Output is correct
27 Correct 31 ms 130396 KB Output is correct
28 Correct 35 ms 130392 KB Output is correct
29 Correct 51 ms 130396 KB Output is correct
30 Correct 49 ms 130548 KB Output is correct