제출 #317867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317867		quocnguyen1012	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	392 ms	174072 KiB

skyscraper

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 105, mod = 1e9 + 7;

int mem[maxn][maxn][1005][2][2];
int ar[maxn], N, L;

void add(int & x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}

int calc(int pos, int cc, int curl, int havel, int haver) {
  int nxtl = curl;
  if (pos)
    nxtl += (havel + haver + 2 * cc) * (ar[pos] - ar[pos - 1]);

  if (nxtl > L)
    return 0;

  if (pos == N - 1) {
    return (cc == 0 ? 1 : 0);
  }
  assert(cc >= 0);

  int & res = mem[pos][cc][curl][havel][haver];
  if (res != -1) return res;

  res = 0;

  /// connect start cc
  add(res, calc(pos + 1, cc, nxtl, 1, haver));

  /// merge with start cc and cc
  if (cc) add(res, (ll)calc(pos + 1, cc - 1, nxtl, 1, haver) * cc % mod);

  /// connect end cc
  add(res, calc(pos + 1, cc, nxtl, havel, 1));
  /// merge with end cc and cc
  if (cc) add(res, (ll)calc(pos + 1, cc - 1, nxtl, havel, 1) * cc % mod);

  /// new cc
  add(res, calc(pos + 1, cc + 1, nxtl, havel, haver));
  /// connect to cc
  add(res, (ll)calc(pos + 1, cc, nxtl, havel, haver) * cc * 2 % mod);
  /// merge 2 cc
  if (cc) add(res, (ll)calc(pos + 1, cc - 1, nxtl, havel, haver) * cc * (cc - 1) % mod);

  return res;
}

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL

  cin >> N >> L;
  for (int i = 0; i < N; ++i) {
    cin >> ar[i];
  }
  sort(ar, ar + N);
  memset(mem, -1, sizeof mem);
  cout << calc(0, 0, 0, 0, 0);
}

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