Submission #134134

#	Time	Username	Problem	Language	Result	Execution time	Memory
134134		Just_Solve_The_Problem	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	353 ms	20200 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int mod = (int)1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}

int mul(int a, int b) {
  return a * 1LL * b % mod;
}

const int N = (int)107;

int dp[N][N][1007][2][2];
int a[N];
int n, L;

main() {
  scanf("%d %d", &n, &L);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  if (n == 1) {
    puts("1");
    return 0;
  }
  sort(a, a + n);
  for (int i = n - 1; i >= 1; i--) {
    a[i] -= a[i - 1];
  }
  a[0] = 0;
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= n; j++) {
      for (int s = 0; s <= L; s++) {
        for (int l = 0; l < 2; l++) {
          for (int r = 0; r < 2; r++) {
            int &res = dp[i][j][s][l][r];
            if (res == 0) continue;
            int nw = s + (2 * j - l - r) * a[i];
            if (nw > L) continue;
            
            if (i) {            
              if (!l) dp[i + 1][j][nw][1][r] = add(dp[i + 1][j][nw][1][r], mul(res, j - (i == n - 1 ? 0 : r)));
              if (!r) dp[i + 1][j][nw][l][1] = add(dp[i + 1][j][nw][l][1], mul(res, j - (i == n - 1 ? 0 : l)));
              dp[i + 1][j][nw][l][r] = add(dp[i + 1][j][nw][l][r], mul(res, 2 * j - l - r));
              
              if (j >= 1) 
                dp[i + 1][j - 1][nw][l][r] = add(dp[i + 1][j - 1][nw][l][r], mul(res, (j - l - r) * (j - 1) + (i == n - 1 ? l * r : 0)));
            }
            
            if (!l) dp[i + 1][j + 1][nw][1][r] = add(dp[i + 1][j + 1][nw][1][r], res);
            if (!r) dp[i + 1][j + 1][nw][l][1] = add(dp[i + 1][j + 1][nw][l][1], res);
            dp[i + 1][j + 1][nw][l][r] = add(dp[i + 1][j + 1][nw][l][r], res);
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= L; i++) {
    ans = add(ans, dp[n][1][i][1][1]);
  }
  printf("%d\n", ans);
}

Compilation message (stderr)

skyscraper.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &L);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

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