oj.uz

Submission #576079

# Submission time Handle Problem Language Result Execution time Memory
576079 2022-06-12T09:13:45 Z hoainiem Skyscraper (JOI16_skyscraper) C++14
15 / 100
 84 ms 184360 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;
  	if (n == 1)
    {
      cout << 0;
      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 Incorrect 83 ms 184280 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 70 ms 184336 KB Output is correct
2 Correct 66 ms 184316 KB Output is correct
3 Correct 73 ms 184360 KB Output is correct
4 Correct 75 ms 184284 KB Output is correct
5 Correct 72 ms 184268 KB Output is correct
6 Correct 77 ms 184336 KB Output is correct
7 Correct 70 ms 184268 KB Output is correct
8 Correct 70 ms 184312 KB Output is correct
9 Correct 75 ms 184288 KB Output is correct
10 Correct 84 ms 184348 KB Output is correct

Subtask #3
0 / 80.0

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