oj.uz

Submission #614449

# Submission time Handle Problem Language Result Execution time Memory
614449 2022-07-31T03:05:09 Z lunchbox Skyscraper (JOI16_skyscraper) C++17
0 / 100
 9 ms 2808 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2808 KB Output is correct
2 Correct 7 ms 2780 KB Output is correct
3 Correct 6 ms 2744 KB Output is correct
4 Correct 6 ms 2772 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 7 ms 2744 KB Output is correct
7 Correct 9 ms 2772 KB Output is correct
8 Correct 7 ms 2772 KB Output is correct
9 Incorrect 6 ms 2772 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -