Submission #1080733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080733		Mamedov	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	1 ms	604 KiB

skyscraper

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

const int MAXN = 102;
const int MAXL = 1003;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN][MAXL][3];
void solve() {
  int n, l;
  cin >> n >> l;
  vi a(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  if (n == 1) {
    cout << (a[1] <= l ? 1 : 0) << ln;
    return;
  }
  sort(a.begin() + 1, a.end());
  dp[0][0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int diff = (i == n ? 0 : a[i + 1] - a[i]);
    for (int j = 0; j < i; ++j) {
      for (int s = 0; s <= l; ++s) {
        for (int k = 0; k < 3; ++k) {
          if (!dp[i - 1][j][s][k]) continue;

          int sum = s + (2 * j + 2 - k) * diff;
          if (sum <= l) dp[i][j + 1][sum][k] = (1ll * (j + 1 - k) * dp[i - 1][j][s][k] + dp[i][j + 1][sum][k]) % MOD; // new group (not an end position)

          if (k < 2) {
            sum = s + (2 * j + 1 - k) * diff;
            if (sum <= l) dp[i][j + 1][sum][k + 1] = (1ll * (2 - k) * dp[i - 1][j][s][k] + dp[i][j + 1][sum][k + 1]) % MOD; // new group (an end position)
          }

          if (j) {
            sum = s + (2 * j - k) * diff;
            if (sum <= l) dp[i][j][sum][k] = (1ll * (2 * j - k) * dp[i - 1][j][s][k] + dp[i][j][sum][k]) % MOD; // next to a group (not an end position)
            if (k < 2) {
              sum = s + (2 * j - k - 1) * diff;
              if (sum <= l) dp[i][j][sum][k + 1] = (1ll * (2 - k) * dp[i - 1][j][s][k] + dp[i][j][sum][k + 1]) % MOD; // next to a group (an end position)
            }
          }
          if (j >= 2) {
            sum = s + (2 * j - 2 - k) * diff;
            if (sum <= l) dp[i][j - 1][sum][k] = (1ll * (j - 1) * dp[i - 1][j][s][k] + dp[i][j - 1][sum][k]) % MOD; // combine two groups
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i <= l; ++i) {
    res += dp[n][1][i][2];
    if (res >= MOD) res -= MOD;
  }
  cout << res << ln;
}
int main() {
  iospeed;
  solve();
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80