Submission #614449

#	Time	Username	Problem	Language	Result	Execution time	Memory
614449		lunchbox	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	9 ms	2808 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 5, L = 1000 + 5, MD = 1000000007;

int main() {
  int n, l;
  scanf("%d%d", &n, &l);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  static int ar[N];
  for (int i = 1; i <= n; i++)
    scanf("%d", &ar[i]);
  sort(ar + 1, ar + n + 1);
  ar[n + 1] = L * 2;
  static int dp[N][L][3];
  dp[0][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    static int dq[N][L][3];
    memset(dq, 0, sizeof dq);
    for (int j = 1; j <= i; j++)
      for (int k = 0; k <= l; k++)
        for (int m = 0; m < 3; m++) {
          int d = (2 * j - m) * (ar[i + 1] - ar[i]);
          if (d > k || i + j + 1 - m > n)
            continue;
          long long s = 0;
          s += dp[j - 1][k - d][m];
          if (m > 0)
            s += (3 - m) * dp[j - 1][k - d][m - 1];
          s += (long long) (2 * j - m) * dp[j][k - d][m];
          if (m == 0)
            s += (long long) j * (j + 1) * dp[j + 1][k - d][m];
          else if (m == 1) {
            s += (long long) 2 * j * dp[j][k - d][m - 1];
            s += (long long) j * j * dp[j + 1][k - d][m];
          } else if (m == 2) {
            if (i == n) {
              s += dp[j][k - d][m - 1];
              s += dp[j + 1][k - d][m];
            } else {
              s += (long long) (j - 1) * dp[j][k - d][m - 1];
              s += (long long) j * (j - 1) * dp[j + 1][k - d][m];
            }
          }
          dq[j][k][m] = s % MD;
        }
    swap(dp, dq);
  }
  long long s = 0;
  for (int i = 0; i <= l; i++)
    s += dp[1][i][2];
  printf("%d\n", (int) s % MD);
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   scanf("%d%d", &n, &l);
      |   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d", &ar[i]);
      |     ~~~~~^~~~~~~~~~~~~~

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