oj.uz

Submission #369567

# Submission time Handle Problem Language Result Execution time Memory
369567 2021-02-21T22:02:01 Z solaimanope Skyscraper (JOI16_skyscraper) C++17
15 / 100
 86 ms 167148 KB 
#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

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

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 167020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 166892 KB Output is correct
2 Correct 85 ms 166892 KB Output is correct
3 Correct 82 ms 166892 KB Output is correct
4 Correct 82 ms 166892 KB Output is correct
5 Correct 85 ms 167148 KB Output is correct
6 Correct 86 ms 166892 KB Output is correct
7 Correct 85 ms 166892 KB Output is correct
8 Correct 82 ms 166892 KB Output is correct
9 Correct 83 ms 166912 KB Output is correct
10 Correct 82 ms 166820 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 167020 KB Output isn't correct
2 Halted 0 ms 0 KB -