Submission #1322597

#TimeUsernameProblemLanguageResultExecution timeMemory
1322597ziad3ssam10Skyscraper (JOI16_skyscraper)C++20
15 / 100
101 ms226920 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<typename T>
using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define wady                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

void files() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
}

const int N = 1e2 + 5, mod = 1e9 + 7;
int dp[N][N][10 * N][5], a[N];
int n, l;

int add(ll a,ll b) { return (a + b) % mod; }
int mul(ll a,ll b) { return (a * b) % mod; }

int rec(int idx,int open,int sum,int last) {
    if (last > 2 or sum > l)return 0;
    if (open == 0 and idx > 1)return 0;
    if (idx == n + 1) {
        return last == 2 and open == 1;
    }
    int &ret = dp[idx][open][sum][last];
    if (~ret)return ret;
    ret = 0;
    int nsum = sum + (a[idx] - a[idx - 1]) * (2 * open - last);
    if (open >= 2) {
        ret = add(ret, mul(open - 1, rec(idx + 1, open - 1, nsum, last)));
    }
    if (open >= 1) {
        ret = add(ret, mul(2 * open - last, rec(idx + 1, open, nsum, last)));
    }
    ret = add(ret, mul(open + 1 - last, rec(idx + 1, open + 1, nsum, last)));
    if (last < 2) {
        ret = add(ret, mul((2 - last), rec(idx + 1, open + 1, nsum, last + 1)));
    }
    if (last < 2) {
        ret = add(ret, mul((2 - last), rec(idx + 1, open, nsum, last + 1)));
    }
    return ret;
}

void solve(int tc) {
    cin >> n >> l;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    memset(dp, -1, sizeof dp);
    cout << rec(1, 0, 0, 0) << endl;
}


signed main() {
    wady
   // files();
    int t = 1;
    //   cin >> t;
    int tc = 1;
    while (t--)
        solve(tc++);
}

Compilation message (stderr)

skyscraper.cpp: In function 'void files()':
skyscraper.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...