Submission #601598

#	Time	Username	Problem	Language	Result	Execution time	Memory
601598		Soumya1	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	152 ms	2648 KiB

skyscraper

#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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80