oj.uz

Submission #1080756

# Submission time Handle Problem Language Result Execution time Memory
1080756 2024-08-29T13:47:03 Z Mamedov Skyscraper (JOI16_skyscraper) C++17
100 / 100
 28 ms 15452 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

const int MAXN = 102;
const int MAXL = 1003;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN][MAXL][3];
void solve() {
  int n, l;
  cin >> n >> l;
  vi a(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  if (n == 1) {
    cout << 1 << ln;
    return;
  }
  sort(a.begin() + 1, a.end());
  dp[0][0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int diff = (i == n ? 0 : a[i + 1] - a[i]);
    for (int j = 0; j < i; ++j) {
      for (int s = 0; s <= l; ++s) {
        for (int k = 0; k < 3; ++k) {
          if (!dp[i - 1][j][s][k]) continue;

          int sum = s + (2 * j + 2 - k) * diff;
          if (sum <= l) dp[i][j + 1][sum][k] = (1ll * (j + 1 - k) * dp[i - 1][j][s][k] + dp[i][j + 1][sum][k]) % MOD; // new group (not an end position)

          if (k < 2) {
            sum = s + (2 * j + 1 - k) * diff;
            if (sum <= l) dp[i][j + 1][sum][k + 1] = (1ll * (2 - k) * dp[i - 1][j][s][k] + dp[i][j + 1][sum][k + 1]) % MOD; // new group (an end position)
          }

          if (j) {
            sum = s + (2 * j - k) * diff;
            if (sum <= l) dp[i][j][sum][k] = (1ll * (2 * j - k) * dp[i - 1][j][s][k] + dp[i][j][sum][k]) % MOD; // next to a group (not an end position)
            if (k < 2) {
              sum = s + (2 * j - k - 1) * diff;
              if (sum <= l) dp[i][j][sum][k + 1] = (1ll * (2 - k) * dp[i - 1][j][s][k] + dp[i][j][sum][k + 1]) % MOD; // next to a group (an end position)
            }
          }
          if (j >= 2) {
            sum = s + (2 * j - 2 - k) * diff;
            if (sum <= l) dp[i][j - 1][sum][k] = (1ll * (j - 1) * dp[i - 1][j][s][k] + dp[i][j - 1][sum][k]) % MOD; // combine two groups
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i <= l; ++i) {
    res += dp[n][1][i][2];
    if (res >= MOD) res -= MOD;
  }
  cout << res << ln;
}
int main() {
  iospeed;
  solve();
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 28 ms 15452 KB Output is correct
23 Correct 22 ms 5572 KB Output is correct
24 Correct 17 ms 8284 KB Output is correct
25 Correct 17 ms 6236 KB Output is correct
26 Correct 15 ms 5940 KB Output is correct
27 Correct 9 ms 7860 KB Output is correct
28 Correct 12 ms 9316 KB Output is correct
29 Correct 19 ms 11356 KB Output is correct
30 Correct 19 ms 6336 KB Output is correct