oj.uz

Submission #576076

# Submission time Handle Problem Language Result Execution time Memory
576076 2022-06-12T09:10:05 Z hoainiem Skyscraper (JOI16_skyscraper) C++14
0 / 100
 80 ms 184352 KB 
    #include <bits/stdc++.h>
    //#pragma GCC target("popcnt")
    #define fi first
    #define se second
    #define lc id<<1
    #define rc id<<1^1
    #define val f[i][j][s][cl][cr]
    const int mod = 1e9 + 7;
    double begintime, endtime;

    using namespace std;
    inline void CALC_TIME()
    {
        endtime = clock();
        cout << "\nexecution time : " << (endtime - begintime + 1) / 1000 << " s";
    }
    void add(int &x, int y)
    {
        x += y;
        if (x >= mod)
            x -= mod;
    }
    int mul(int x, int y)
    {
        return 1LL * x * y % mod;
    }
    typedef pair<int, int> pii;
    int n, k, a[108], f[108][108][1008][2][2];
    int dq(int i, int j, int s, int cl, int cr)
    {
        if (s > k || (!j && i))
            return 0;
        if (val != -1)
            return val;
        if (i >= n)
            return val = (s == k && j == 1 && cl && cr);
        int res = 0;
        add(res, mul(j + 1 - cl - cr, dq(i + 1, j + 1, s + (j * 2 + 2 - cl - cr) * a[i + 1], cl, cr)));
        if (!cl)
            add(res, dq(i + 1, j + 1, s + (j * 2 + 1 - cr) * a[i + 1], 1, cr));
        if (!cr)
            add(res, dq(i + 1, j + 1, s + (j * 2 + 1 - cl) * a[i + 1], cl, 1));
        if (j > 0)
            add(res, mul(j * 2 - cl - cr, dq(i + 1, j, s + (j * 2 - cl - cr) * a[i + 1], cl, cr)));
        if (!cl)
            add(res, dq(i + 1, j, s + (j * 2 - 1 - cr) * a[i + 1], 1, cr));
        if (!cr)
            add(res, dq(i + 1, j, s + (j * 2 - 1 - cl) * a[i + 1], cl, 1));
        if (j > 1)
            add(res, mul(j - 1, dq(i + 1, j - 1, s + (j * 2 - 2 - cl - cr) * a[i + 1], cl, cr)));
        return val = res;
    }   
    int main()
    {
        begintime = clock();
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        memset(f, -1, sizeof(f));
        cin >> n >> k;
        if (n == 1)
        {
            cout << 1;
            return 0;
        }
        for (int i = 0; i < n; i++)
            cin >> a[i];
        sort(a, a + n);
        a[n] = 0;
        for (int i = n - 1; i > 0; i--)
            a[i] -= a[i - 1];
        a[0] = 0;
        cout << dq(0, 0, 0, 0, 0);
        return 0;
    }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 184352 KB Output is correct
2 Correct 67 ms 184260 KB Output is correct
3 Incorrect 79 ms 184256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 184352 KB Output is correct
2 Correct 67 ms 184260 KB Output is correct
3 Incorrect 79 ms 184256 KB Output isn't correct
4 Halted 0 ms 0 KB -