Submission #1147022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147022		iah	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	95 ms	122696 KiB

skyscraper

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

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

const int nmax = 100;
const int mod = 1e9 + 7;
int a[nmax + 7];
ll dp[nmax + 7][nmax + 7][1000 + 7][3];

signed main() {
  for(string s: {NAME, ""}) {
    if (fopen((s + ".inp").c_str(), "r")) {
      freopen((s + ".inp").c_str(), "r", stdin);
      freopen((s + ".out").c_str(), "w", stdout);
      break;
    }
  }
  cin.tie(0)->sync_with_stdio(0);

  int n, lim;
  cin >> n >> lim;

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

  FOR(i, 1, n) {
    cin >> a[i];
  }

  sort(a + 1, a + n + 1);

  FOR(head, 0, 1) {
    dp[1][1][0][head] = mask(head);
  }

  FOR(i, 2, n) {
    int diff = a[i] - a[i - 1];

    FOR(comp, 1, i - 1) {
      FOR(sum, 0, lim) {
        FOR(head, 0, 2) {
          int nsum = sum + diff * (2 * comp - head);
          if (nsum > lim) {
            continue;
          }

          dp[i][comp - 1][nsum][head] += dp[i - 1][comp][sum][head] * (comp - 1);
          dp[i][comp][nsum][head] += dp[i - 1][comp][sum][head] * (2 * comp - head);
          dp[i][comp + 1][nsum][head] += dp[i - 1][comp][sum][head] * (comp + 1 - head);

          if (head < 2) {
            dp[i][comp][nsum][head + 1] += dp[i - 1][comp][sum][head] * (2 - head);
            dp[i][comp + 1][nsum][head + 1] += dp[i - 1][comp][sum][head] * (2 - head);
          }
        }
      }
    }

    FOR(comp, 1, i) {
      FOR(sum, 0, lim) {
        FOR(head, 0, 2) {
          dp[i][comp][sum][head] %= mod;
        }
      }
    }
  }

  ll ans = 0;
  FOR(i, 0, lim) {
//    cout << i << " " << dp[n][1][i][2] << "\n";

    ans += dp[n][1][i][2];
    ans %= mod;
  }

  cout << ans;

  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |       freopen((s + ".inp").c_str(), "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:26:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |       freopen((s + ".out").c_str(), "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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