oj.uz

답안 #576074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
576074 2022-06-12T09:07:12 Z hoainiem Skyscraper (JOI16_skyscraper) C++14
15 / 100
 79 ms 184492 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 = (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;
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 184292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 184336 KB Output is correct
2 Correct 68 ms 184332 KB Output is correct
3 Correct 74 ms 184320 KB Output is correct
4 Correct 67 ms 184320 KB Output is correct
5 Correct 79 ms 184372 KB Output is correct
6 Correct 77 ms 184324 KB Output is correct
7 Correct 71 ms 184368 KB Output is correct
8 Correct 67 ms 184292 KB Output is correct
9 Correct 69 ms 184376 KB Output is correct
10 Correct 67 ms 184492 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 184292 KB Output isn't correct
2 Halted 0 ms 0 KB -