Submission #1047093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047093		nima_aryan	Skyscraper (JOI16_skyscraper)	C++14	Compilation error	0 ms	0 KiB

skyscraper

/**
 *    author:  NimaAryan
 *    created: 2024-06-26 20:39:48
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 mod = 1E9 + 7;

void add(i64& x, i64 y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, L;
  cin >> N >> L;

  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

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

  sort(A.begin(), A.end());
  int M = 2000;
  int T = M + 1 + M;
  vector f(3, vector(N + 1, vector<i64>(T + 1)));
  f[0][1][0] = 1;
  f[1][1][-A[0] + M] = 2;
  f[2][1][2 * -A[0] + M] = 1;
  for (int i = 1; i < N; ++i) {
    vector g(3, vector(N + 1, vector<i64>(T + 1)));
    for (int c = 1; c <= N; ++c) {
      for (int s = 0; s <= T; ++s) {
        if (c + 1 <= N && s - 2 * A[i] >= 0) {
          add(g[0][c + 1][s - 2 * A[i]], f[0][c][s] * max(0, c - 1) % mod);
          add(g[1][c + 1][s - 2 * A[i]], f[1][c][s] * c % mod);
          add(g[2][c + 1][s - 2 * A[i]], f[2][c][s] * (c + 1) % mod);
        }
        add(g[0][c][s], f[0][c][s] * max(0, 2 * c - 2) % mod);
        add(g[1][c][s], f[1][c][s] * max(0, 2 * c - 1) % mod);
        add(g[2][c][s], f[2][c][s] * 2 * c % mod);
        if (c + 1 <= N && s - A[i] >= 0) {
          add(g[0][c + 1][s - A[i]], f[1][c][s]);
          add(g[1][c + 1][s - A[i]], f[2][c][s] * 2 % mod);
        }
        if (s + A[i] <= T) {
          add(g[0][c][s + A[i]], f[1][c][s]);
          add(g[1][c][s + A[i]], f[2][c][s] * 2 % mod);
        }
        if (c - 1 >= 0 && s + 2 * A[i] <= T) {
          add(g[0][c - 1][s + 2 * A[i]], f[0][c][s] * max(0, c - 1) % mod);
          add(g[1][c - 1][s + 2 * A[i]], f[1][c][s] * max(0, c - 1) % mod);
          add(g[2][c - 1][s + 2 * A[i]], f[2][c][s] * max(0, c - 1) % mod);
        }
      }
    }
    f.swap(g);
  }

  i64 ans = 0;
  for (int l = 0; l <= L; ++l) {
    add(ans, f[0][1][l + M]);
  }
  cout << ans << "\n";

  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:43:10: error: missing template arguments before 'f'
   43 |   vector f(3, vector(N + 1, vector<i64>(T + 1)));
      |          ^
skyscraper.cpp:44:3: error: 'f' was not declared in this scope
   44 |   f[0][1][0] = 1;
      |   ^
skyscraper.cpp:48:12: error: missing template arguments before 'g'
   48 |     vector g(3, vector(N + 1, vector<i64>(T + 1)));
      |            ^
skyscraper.cpp:52:15: error: 'g' was not declared in this scope
   52 |           add(g[0][c + 1][s - 2 * A[i]], f[0][c][s] * max(0, c - 1) % mod);
      |               ^
skyscraper.cpp:56:13: error: 'g' was not declared in this scope
   56 |         add(g[0][c][s], f[0][c][s] * max(0, 2 * c - 2) % mod);
      |             ^
skyscraper.cpp:74:12: error: 'g' was not declared in this scope
   74 |     f.swap(g);
      |            ^