oj.uz

Submission #601598

# Submission time Handle Problem Language Result Execution time Memory
601598 2022-07-22T08:29:40 Z Soumya1 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 152 ms 2648 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mod = 1000000007;
int dp[101][1001][3];
int new_dp[101][1001][3];
void testCase() {
  int n, l;
  cin >> n >> l;
  vector<int> a(n);
  for (int &i : a) cin >> i;
  if (n == 1) {
    cout << "1\n";
    return;
  }
  auto add = [&](int a, int b) { return (a + b) % mod; };
  auto mul = [&](int a, int b) { return (1LL * a * b) % mod; };
  auto add_self = [&](int &a, int b) { (a += b) %= mod; };
  sort(a.begin(), a.end());
  dp[1][0][0] = 1;
  dp[1][0][1] = 2;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
      for (int s = 0; s <= l; s++) {
        for (int c = 0; c < 3; c++) {
          int v = (a[i] - a[i - 1]) * (2 * j - c);
          if (s + v > l) continue;
          // add new component
          add_self(new_dp[j + 1][s + v][c], mul(dp[j][s][c], j + 1 - c));
          // combine two components
          add_self(new_dp[j - 1][s + v][c], mul(dp[j][s][c], j - 1));
          // add to the beginning or end of one already available component
          add_self(new_dp[j][s + v][c], mul(dp[j][s][c], 2 * j - c));
          // create end
          add_self(new_dp[j + 1][s + v][c + 1], mul(dp[j][s][c], 2 - c));
          // create end and merge
          add_self(new_dp[j][s + v][c + 1], mul(dp[j][s][c], 2 - c));
        }
      }
    }
    for (int j = 1; j <= i + 1; j++) {
      for (int s = 0; s <= l; s++) {
        for (int c = 0; c < 3; c++) {
          // debug(i, j, s, c, new_dp[j][s][c]);
          dp[j][s][c] = new_dp[j][s][c];
          new_dp[j][s][c] = 0;
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= l; i++) {
    add_self(ans, dp[1][i][2]);
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
}

Compilation message

skyscraper.cpp: In function 'void testCase()':
skyscraper.cpp:18:8: warning: variable 'add' set but not used [-Wunused-but-set-variable]
   18 |   auto add = [&](int a, int b) { return (a + b) % mod; };
      |        ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 102 ms 2100 KB Output is correct
23 Correct 152 ms 2648 KB Output is correct
24 Correct 112 ms 2544 KB Output is correct
25 Correct 128 ms 2616 KB Output is correct
26 Correct 111 ms 2632 KB Output is correct
27 Correct 50 ms 1620 KB Output is correct
28 Correct 65 ms 1748 KB Output is correct
29 Correct 107 ms 2364 KB Output is correct
30 Correct 128 ms 2636 KB Output is correct