oj.uz

답안 #681740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681740 2023-01-14T02:21:07 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 98 ms 130516 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;
}
// https://oj.uz/problem/view/JOI16_skyscraper

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 47 ms 130356 KB Output is correct
3 Correct 48 ms 130376 KB Output is correct
4 Correct 47 ms 130372 KB Output is correct
5 Correct 47 ms 130292 KB Output is correct
6 Correct 46 ms 130380 KB Output is correct
7 Correct 46 ms 130336 KB Output is correct
8 Correct 52 ms 130404 KB Output is correct
9 Correct 48 ms 130388 KB Output is correct
10 Correct 47 ms 130328 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 130352 KB Output is correct
2 Correct 48 ms 130360 KB Output is correct
3 Correct 47 ms 130368 KB Output is correct
4 Correct 47 ms 130380 KB Output is correct
5 Correct 48 ms 130328 KB Output is correct
6 Correct 48 ms 130404 KB Output is correct
7 Correct 46 ms 130460 KB Output is correct
8 Correct 47 ms 130380 KB Output is correct
9 Correct 48 ms 130380 KB Output is correct
10 Correct 48 ms 130340 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 47 ms 130356 KB Output is correct
3 Correct 48 ms 130376 KB Output is correct
4 Correct 47 ms 130372 KB Output is correct
5 Correct 47 ms 130292 KB Output is correct
6 Correct 46 ms 130380 KB Output is correct
7 Correct 46 ms 130336 KB Output is correct
8 Correct 52 ms 130404 KB Output is correct
9 Correct 48 ms 130388 KB Output is correct
10 Correct 47 ms 130328 KB Output is correct
11 Correct 47 ms 130352 KB Output is correct
12 Correct 48 ms 130360 KB Output is correct
13 Correct 47 ms 130368 KB Output is correct
14 Correct 47 ms 130380 KB Output is correct
15 Correct 48 ms 130328 KB Output is correct
16 Correct 48 ms 130404 KB Output is correct
17 Correct 46 ms 130460 KB Output is correct
18 Correct 47 ms 130380 KB Output is correct
19 Correct 48 ms 130380 KB Output is correct
20 Correct 48 ms 130340 KB Output is correct
21 Correct 49 ms 130368 KB Output is correct
22 Correct 98 ms 130300 KB Output is correct
23 Correct 78 ms 130516 KB Output is correct
24 Correct 91 ms 130324 KB Output is correct
25 Correct 78 ms 130356 KB Output is correct
26 Correct 73 ms 130380 KB Output is correct
27 Correct 68 ms 130384 KB Output is correct
28 Correct 68 ms 130512 KB Output is correct
29 Correct 84 ms 130380 KB Output is correct
30 Correct 78 ms 130372 KB Output is correct