제출 #576077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
576077		hoainiem	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	261 ms	184396 KiB

skyscraper

#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 = (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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80