Submission #1094352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094352		Mike_Vu	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	188 ms	260748 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*2][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);
    memset(dp, 0, sizeof(dp));
    dp[0][0][maxl][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int r = 0; r <= maxl+l; r++) {
                for (int k = 0; k < 3; k++) {
                    if (!dp[i][j][r][k]) continue;
                    //horizontal
                    //join
                    if (r+2*a[i+1] <= maxl+l && j > 1) ad(dp[i+1][j-1][r+2*a[i+1]][k], mul(dp[i][j][r][k], j-1));
                    //con
                    if (j > 0) ad(dp[i+1][j][r][k], mul(dp[i][j][r][k], 2*j-k));
                    //new
                    if (r-2*a[i+1] >= 0) ad(dp[i+1][j+1][r-2*a[i+1]][k], mul(dp[i][j][r][k], j+1-k));
                    //edge
                    if (k < 2) {
                        //con
                        if (r+a[i+1] <= maxl+l && j > 0) ad(dp[i+1][j][r+a[i+1]][k+1], mul(dp[i][j][r][k], 2-k));
                        //new
                        if (r-a[i+1] >= 0) ad(dp[i+1][j+1][r-a[i+1]][k+1], mul(dp[i][j][r][k], 2-k));
                    }
//                    cout << i << ' ' << j << ' ' << r << ' ' << r-maxl << ' ' << k << ' ' << dp[i][j][r][k] << "\n";
                }
            }
        }
    }
    int res = 0;
    for (int r = 0; r <= maxl+l; r++) {
        ad(res, dp[n][1][r][2]);
    }
    cout << res;
}
/*
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: 0 / 80