Submission #1094435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094435		Mike_Vu	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	91 ms	130528 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

namespace modulofunc{
    const int mod = 1e9+7;
    void ad(int &x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        x = temp;
    }
    int add(int x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        return temp;
    }
    int sub(int x, int y) {
        ll temp = x-y;
        if (temp < 0) temp += mod;
        return temp;
    }
    int mul(int x, int y) {
        return 1LL*x*y%mod;
    }
}
using namespace modulofunc;

const int maxn = 105, maxl = 1005;
int n, l, a[maxn];
int dp[maxn][maxn][maxl][3];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << 1;
        return 0;
    }
    sort(a+1, a+n+1);
    a[n+1] = l+1;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int r = 0; r <= l; r++) {
                for (int k = 0; k < 3; k++) {
                    if (!dp[i][j][r][k]) continue;
                    int &ret = dp[i][j][r][k];
                    int temp = a[i+2]-a[i+1];
                    //horizontal
                    //join
                    if (j > 1 && r+(2*(j-1)-k)*temp <= l) ad(dp[i+1][j-1][r+(2*(j-1)-k)*temp][k], mul(ret, j-1));
                    //con
                    if (j > 0 && r+(2*j-k)*temp <= l) ad(dp[i+1][j][r+(2*j-k)*temp][k], mul(ret, 2*j-k));
                    //new
                    if (r+(2*(j+1)-k)*temp <= l)ad(dp[i+1][j+1][r+(2*(j+1)-k)*temp][k], mul(ret, j+1-k));
                    //edge
                    if (k < 2) {
                        //con
                        if (j > 0 && r+(2*j-k-1)*temp <= l) ad(dp[i+1][j][r+(2*j-k-1)*temp][k+1], mul(ret, 2-k));
                        //new
                        if (r+(2*(j+1)-k-1)*temp <= l) ad(dp[i+1][j+1][r+(2*(j+1)-k-1)*temp][k+1], mul(ret, 2-k));
                    }
//                    cout << i << ' ' << j << ' ' << r << ' ' << r-maxl << ' ' << k << ' ' << ret << "\n";
                }
            }
        }
    }
    int res = 0;
    for (int r = 0; r <= l; r++) {
        ad(res, dp[n][1][r][2]);
    }
    cout << res;
}
/*
3 793
832 436 766

4 10
3 6 2 9
8 35
3 7 1 5 10 2 11 6
*/

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