제출 #498604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498604		600Mihnea	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	1874 ms	25668 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

int mul(int a, int b) {
  return a * (ll) b % M;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

const int N = 100 + 7;
const int Z = 4000 + 7;
int n;
int limit;
int a[N];
int dp[N][2 * Z][2][2]; /// ways[islands][sum]
int nwdp[N][2 * Z][2][2];

void rst() {
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < 2 * Z; j++) {
      for (int bg = 0; bg < 2; bg++) {
        for (int nd = 0; nd < 2; nd++) {
          dp[i][j][bg][nd] = nwdp[i][j][bg][nd];
          nwdp[i][j][bg][nd] = 0;
        }
      }
    }
  }
}

void addTo(int islands, int real_sum, int bg, int nd, int value) {
  if (islands >= 1 && -(Z - 1) <= real_sum && real_sum <= (Z - 1)) {
    addup(nwdp[islands][real_sum + Z][bg][nd], value);
  }
}

int main() {
  bool isHome;

  isHome = true;
  isHome = false;

  if (isHome) {
    freopen ("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0); cin.tie(0);
  }


  cin >> n >> limit;


  if (n == 1) {
    cout << "1\n";
    return 0;
  }

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);

  /// it is the first

  dp[1][Z - a[1]][1][0] = 1;

  /// it is the last


  dp[1][Z - a[1]][0][1] = 1;

  /// it is in the middle


  dp[1][Z - 2 * a[1]][0][0] = 1;

  for (int it = 2; it <= n; it++) {
    int x = a[it];
    for (int islands = 1; islands < it; islands++) {
      for (int sum = -(Z - 1); sum <= (Z - 1); sum++) {
        for (int bg = 0; bg < 2; bg++) {
          for (int nd = 0; nd < 2; nd++) {
            int dp_value = dp[islands][sum + Z][bg][nd];
            if (dp_value == 0) {
              continue;
            }

            { /// create a new island

              /// make it the first

              if (bg == 0) {
                addTo(islands + 1, sum - x, 1, nd, dp_value);
              }

              /// make it the last

              if (nd == 0) {
                addTo(islands + 1, sum - x, bg, 1, dp_value);
              }

              /// place it in the middle

              int total_ways = (islands + 1) - bg - nd;

              addTo(islands + 1, sum - 2 * x, bg, nd, mul(dp_value, total_ways));

            }

            { /// put it next to some guy


              /// make it the first

              if (bg == 0) {
                addTo(islands, sum + x, 1, nd, dp_value);
              }

              /// make it the last

              if (nd == 0) {
                addTo(islands, sum + x, bg, 1, dp_value);
              }


              /// place it in the middle

              int total_ways = 2 * islands - bg - nd;

              addTo(islands, sum, bg, nd, mul(dp_value, total_ways));

            }

            if (islands >= 2) { /// join some guys

              int total_ways = (islands - 1);

              addTo(islands - 1, sum + 2 * x, bg, nd, mul(dp_value, total_ways));
            }

          }
        }
      }
    }
    rst();
  }


  int sol = 0;

  for (int sum = 0; sum <= limit; sum++) {
    int dp_value = dp[1][sum + Z][1][1];
    if (dp_value) {
      addup(sol, dp_value);
    }
  }

  cout << sol << "\n";


  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:62:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen ("input", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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