Submission #375443

#	Time	Username	Problem	Language	Result	Execution time	Memory
375443		spatarel	Skyscraper (JOI16_skyscraper)	C++17	5 / 100	17 ms	1900 KiB

skyscraper

#include <stdio.h>
#include <algorithm>

const int MOD = 1'000'000'007;

const int MAX_N = 100;
const int MAX_L = 1000;

long long Count[1 + MAX_N][1 + MAX_N + 1][1 + MAX_L][1 + 2 + 1];

void addSelf(long long &a, long long b) {
  a = (a + b) % MOD;
}

int main() {
  int N, L;
  scanf("%d%d", &N, &L);
  int A[1 + N];
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
  }
  std::sort(A + 1, A + N + 1);
  Count[0][0][0][0] = 1;
  for (int i = 0; i + 1 <= N; i++) {
    for (int d = 0; d <= N; d++) {
      for (int l = 0; l <= L; l++) {
        for (int e = 0; e <= 2; e++) {
          int newL = l + (2 * d - e) * (A[i + 1] - A[i]);
          if (0 <= newL && newL <= L) {
            addSelf(Count[i + 1][d + 1][newL][e]    , (d + 1 - e) * Count[i][d][l][e]); // valley
            if (0 <= d - 1) {
            addSelf(Count[i + 1][d - 1][newL][e]    , (d - 1)     * Count[i][d][l][e]); // peak
            }
            addSelf(Count[i + 1][d + 0][newL][e]    , (2 * d - e) * Count[i][d][l][e]); // edge
            addSelf(Count[i + 1][d + 0][newL][e + 1], (2 - e)     * Count[i][d][l][e]); // edge ending
            addSelf(Count[i + 1][d + 1][newL][e + 1], (2 - e)     * Count[i][d][l][e]); // valley ending
          }
        }
      }
    }
  }
  long long answer = 0;
  for (int l = 0; l <= L; l++) {
    addSelf(answer, Count[N][1][l][2]);
  }
  if (N == 1) {
    answer = 1;
  }
  printf("%lld\n", answer);
  return 0;
}

Compilation message (stderr)

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

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