oj.uz

Submission #941402

# Submission time Handle Problem Language Result Execution time Memory
941402 2024-03-08T17:52:52 Z Hacv16 Skyscraper (JOI16_skyscraper) C++17
20 / 100
 438 ms 91200 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 14;
const int MAXL = 101;
const int MOD = 1e9 + 7;

int n, l, a[MAXN];
int dp[1 << MAXN][MAXN][MAXL];

int32_t main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> l;

    for(int i = 0; i < n; i++)
        cin >> a[i];

    if(n <= 10)
    {
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);

        int ans = 0;

        do{
            vector<int> curPerm;

            for(int i = 0; i < n; i++)
                curPerm.push_back(a[ p[i] ]);

            int curVal = 0;
            for(int i = 1; i < n; i++)
                curVal += abs(a[ p[i] ] - a[ p[i - 1] ]);

            if(curVal <= l) ans++;

        } while(next_permutation(p.begin(), p.end()));

        cout << ans << '\n';
        return 0;
    }

    for(int i = 0; i < n; i++)
        dp[(1 << i)][i][0] = 1;

    for(int mask = 1; mask < (1 << n); mask++)
    {
        for(int last = 0; last < n; last++)
        {
            if((mask & (1 << last)) == 0) continue;

            for(int pen = 0; pen <= l; pen++)
            {
                for(int prev = 0; prev < n; prev++)
                {
                    if((mask & (1 << prev)) == 0 || prev == last) continue;

                    int curPen = abs(a[last] - a[prev]);

                    if(curPen <= pen)
                        dp[mask][last][pen] = (dp[mask][last][pen] + dp[mask ^ (1 << last)][prev][pen - curPen]) % MOD;
                }
            }
        }
    }

    int ans = 0;

    for(int i = 0; i < n; i++)
        for(int j = 0; j <= l; j++)
            ans = (ans + dp[(1 << n) - 1][i][j]) % MOD;

    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22868 KB Output is correct
2 Correct 398 ms 90964 KB Output is correct
3 Correct 234 ms 90960 KB Output is correct
4 Correct 438 ms 90964 KB Output is correct
5 Correct 394 ms 91200 KB Output is correct
6 Correct 404 ms 91020 KB Output is correct
7 Correct 195 ms 90964 KB Output is correct
8 Correct 223 ms 90996 KB Output is correct
9 Correct 302 ms 90888 KB Output is correct
10 Correct 353 ms 90976 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 50 ms 22868 KB Output is correct
12 Correct 398 ms 90964 KB Output is correct
13 Correct 234 ms 90960 KB Output is correct
14 Correct 438 ms 90964 KB Output is correct
15 Correct 394 ms 91200 KB Output is correct
16 Correct 404 ms 91020 KB Output is correct
17 Correct 195 ms 90964 KB Output is correct
18 Correct 223 ms 90996 KB Output is correct
19 Correct 302 ms 90888 KB Output is correct
20 Correct 353 ms 90976 KB Output is correct
21 Incorrect 18 ms 22876 KB Output isn't correct
22 Halted 0 ms 0 KB -