oj.uz

Submission #1047094

# Submission time Handle Problem Language Result Execution time Memory
1047094 2024-08-07T08:52:04 Z nima_aryan Skyscraper (JOI16_skyscraper) C++17
20 / 100
 856 ms 22896 KB 
/**
 *    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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 5 ms 1964 KB Output is correct
5 Correct 4 ms 2464 KB Output is correct
6 Correct 4 ms 2452 KB Output is correct
7 Correct 7 ms 2452 KB Output is correct
8 Correct 5 ms 2452 KB Output is correct
9 Correct 4 ms 2360 KB Output is correct
10 Correct 6 ms 2456 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3324 KB Output is correct
2 Correct 16 ms 3756 KB Output is correct
3 Correct 16 ms 3780 KB Output is correct
4 Correct 23 ms 3788 KB Output is correct
5 Correct 15 ms 3780 KB Output is correct
6 Correct 22 ms 3756 KB Output is correct
7 Correct 15 ms 3780 KB Output is correct
8 Correct 15 ms 3776 KB Output is correct
9 Correct 15 ms 3780 KB Output is correct
10 Correct 15 ms 3756 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 5 ms 1964 KB Output is correct
5 Correct 4 ms 2464 KB Output is correct
6 Correct 4 ms 2452 KB Output is correct
7 Correct 7 ms 2452 KB Output is correct
8 Correct 5 ms 2452 KB Output is correct
9 Correct 4 ms 2360 KB Output is correct
10 Correct 6 ms 2456 KB Output is correct
11 Correct 13 ms 3324 KB Output is correct
12 Correct 16 ms 3756 KB Output is correct
13 Correct 16 ms 3780 KB Output is correct
14 Correct 23 ms 3788 KB Output is correct
15 Correct 15 ms 3780 KB Output is correct
16 Correct 22 ms 3756 KB Output is correct
17 Correct 15 ms 3780 KB Output is correct
18 Correct 15 ms 3776 KB Output is correct
19 Correct 15 ms 3780 KB Output is correct
20 Correct 15 ms 3756 KB Output is correct
21 Correct 124 ms 9428 KB Output is correct
22 Correct 522 ms 17880 KB Output is correct
23 Correct 832 ms 22896 KB Output is correct
24 Incorrect 856 ms 22668 KB Output isn't correct
25 Halted 0 ms 0 KB -