oj.uz

Submission #1079275

# Submission time Handle Problem Language Result Execution time Memory
1079275 2024-08-28T12:33:19 Z boris_mihov Skyscraper (JOI16_skyscraper) C++17
100 / 100
 817 ms 81124 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100 + 10;
const int MAXL = 1000 + 10;
const int MOD  = 1e9 + 7;

int n, l;
int a[MAXN];
int prefix[MAXN];
std::unordered_map <int,int> dp[MAXN][MAXN][2][2];

int f(int idx, int count, int sum, bool foundB, bool foundE)
{   
    if (idx + count - 2 > n || sum + 2 * (prefix[idx + count - 2] - prefix[idx - 1]) > l)
    {
        return 0;
    }

    if (idx == n + 1)
    {
        assert(count == 1 && sum <= l);
        return foundB && foundE;
    }

    if (dp[idx][count][foundB][foundE].count(sum))
    {
        return dp[idx][count][foundB][foundE][sum];
    }

    llong res = f(idx + 1, count + 1, sum - 2 * a[idx], foundB, foundE);
    if (!foundB)
    {
        res += f(idx + 1, count + 1, sum - a[idx], 1, foundE);
    }

    if (!foundE)
    {
        res += f(idx + 1, count + 1, sum - a[idx], foundB, 1);
    }

    if (count >= 1) 
    {
        res += (2LL * count - foundB - foundE) * f(idx + 1, count, sum, foundB, foundE);
        if (!foundB)
        {
            res += 1LL * (count - foundE) * f(idx + 1, count, sum + a[idx], 1, foundE);
            if (foundE && count == 1 && idx == n)
            {
                res += f(idx + 1, count, sum + a[idx], 1, foundE);
            }
        }

        if (!foundE)
        {
            res += 1LL * (count - foundB) * f(idx + 1, count, sum + a[idx], foundB, 1);
            if (foundB && count == 1 && idx == n)
            {
                res += f(idx + 1, count, sum + a[idx], foundB, 1);
            }
        }
    }

    if (count >= 2) 
    {
        int cntFree = count - foundB - foundE;
        res += 1LL * cntFree * (cntFree - 1) * f(idx + 1, count - 1, sum + 2 * a[idx], foundB, foundE);

        if (foundB)
        {
            res += 1LL * (count - 1 - foundE) * f(idx + 1, count - 1, sum + 2 * a[idx], foundB, foundE);
        }

        if (foundE)
        {
            res += 1LL * (count - 1 - foundB) * f(idx + 1, count - 1, sum + 2 * a[idx], foundB, foundE);
        }

        if (foundB && foundE && idx == n)
        {
            res += f(idx + 1, count - 1, sum + 2 * a[idx], foundB, foundE);
        }
    }

    return dp[idx][count][foundB][foundE][sum] = res % MOD;
}

void solve()
{
    if (n == 1)
    {
        std::cout << 1 << '\n';
        return;
    }

    std::sort(a + 1, a + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }

    std::cout << f(1, 0, 0, 0, 0) << '\n';
}

void input()
{
    std::cin >> n >> l;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base:: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3116 KB Output is correct
10 Correct 2 ms 3108 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3160 KB Output is correct
4 Correct 3 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 3 ms 3420 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3116 KB Output is correct
10 Correct 2 ms 3108 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 2 ms 3160 KB Output is correct
14 Correct 3 ms 3164 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct
16 Correct 3 ms 3420 KB Output is correct
17 Correct 2 ms 3160 KB Output is correct
18 Correct 2 ms 3164 KB Output is correct
19 Correct 3 ms 3164 KB Output is correct
20 Correct 3 ms 3164 KB Output is correct
21 Correct 4 ms 3676 KB Output is correct
22 Correct 817 ms 81124 KB Output is correct
23 Correct 619 ms 69712 KB Output is correct
24 Correct 631 ms 67668 KB Output is correct
25 Correct 647 ms 70208 KB Output is correct
26 Correct 535 ms 61780 KB Output is correct
27 Correct 160 ms 26452 KB Output is correct
28 Correct 230 ms 35880 KB Output is correct
29 Correct 612 ms 65620 KB Output is correct
30 Correct 645 ms 72808 KB Output is correct