Submission #369568

#	Time	Username	Problem	Language	Result	Execution time	Memory
369568		solaimanope	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	339 ms	167068 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int sum(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
void sumi(int &a, int b) {
    a = sum(a, b);
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + MOD : a - b;
}
int mul(int a, int b) {
    return (1LL*a*b)%MOD;
}

const int MAXN = 103, MAXL = 1003;
int ar[MAXN];

int dp[MAXN][MAXN][2][2][MAXL];
int n, l;

int solve(int ps, int open, int bam, int dan, int x) {
    if (x > l) return 0;
//    if (x < 0) {
//        cout << "[" << ps << "][" << open << "][" << bam << "][" << dan << "][" << x << "]" << endl;
//    }
    assert(x >= 0);
    if (ps == n) {
        if (open == 1) return bam ^ dan;
        if (open == 2) return bam & dan;
        return 0;
    }

    int &ans = dp[ps][open][bam][dan][x];
    if (ans != -1) return ans;
    ans = 0;

    int y = open*2-bam-dan;
    int z = ar[ps+1]-ar[ps];

//    vector< string >vs;
//    int b4 = 0;

    ///single comp inside
    sumi(ans, solve(ps+1, open+1, bam, dan, x+y*z+2*z));
//    if (ans != b4) {
//        vs.push_back("single comp inside");
//        b4 = ans;
//    }

    ///single comp border
    if (!bam) sumi(ans, solve(ps+1, open+1, 1, dan, x+y*z+z));
//    if (ans != b4) {
//        vs.push_back("single comp border bam");
//        b4 = ans;
//    }
    if (!dan) sumi(ans, solve(ps+1, open+1, bam, 1, x+y*z+z));
//    if (ans != b4) {
//        vs.push_back("single comp border dan");
//        b4 = ans;
//    }

    ///extend one side of a comp inside
    if (open > 0) sumi(ans, mul(open*2-bam-dan, solve(ps+1, open, bam, dan, x+y*z)));
//    if (ans != b4) {
//        vs.push_back("extend one side of a comp inside");
//        b4 = ans;
//    }

    ///extend one side of a comp border
    if (!bam && open > dan) sumi(ans, mul(open-dan, solve(ps+1, open, 1, dan, x+y*z-z)));
//    if (ans != b4) {
//        vs.push_back("extend one side of a comp border bam");
//        b4 = ans;
//    }
    if (!dan && open > bam) sumi(ans, mul(open-bam, solve(ps+1, open, bam, 1, x+y*z-z)));
//    if (ans != b4) {
//        vs.push_back("extend one side of a comp border dan");
//        b4 = ans;
//    }

    ///glue two comps
    if (open >= 2) {
        int ways = (open-dan)*(open-bam)-bam*dan-(open-bam-dan);
        if (ways > 0) sumi(ans, mul(ways, solve(ps+1, open-1, bam, dan, x+y*z-2*z)));
    }
//    if (ans != b4) {
//        vs.push_back("glue two comps");
//        b4 = ans;
//    }

//    for (string s : vs) cout << s << " | ";
//    cout << endl;
//    cout << "dp[" << ps << "][" << open << "][" << bam << "][" << dan << "][" << x << "] = " << ans << endl;
    return ans;
}

int main() {
    cin >> n >> l;

    for (int i = 1; i <= n; i++) cin >> ar[i];
    sort(ar+1, ar+n+1);

    ///handle n == 1
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }

    memset(dp, -1, sizeof dp);
    cout << solve(1, 0, 0, 0, 0) << endl;

    return 0;
}

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