oj.uz

Submission #971222

# Submission time Handle Problem Language Result Execution time Memory
971222 2024-04-28T08:01:16 Z Beerus13 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 333 ms 487920 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define bit(mask, i) ((mask >> (i)) & 1)
const int N = 1e2 + 5; 
const int mod = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
}

int n, L, a[N];
int dp[1 << 14][14][1005];

void solve() {
    cin >> n >> L;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        dp[1 << i][i][0] = 1;
    }
    for(int mask = 1; mask < (1 << n); ++mask) {
        for(int i = 0; i < n; ++i) if(bit(mask, i)) {
            for(int j = 0; j < n; ++j) if(!bit(mask, j)) {
                for(int diff = 0; diff + abs(a[i] - a[j]) <= L; ++diff) {
                    add(dp[mask | (1 << j)][j][diff + abs(a[i] - a[j])], dp[mask][i][diff]);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int diff = 0; diff <= L; ++diff) add(ans, dp[(1 << n) - 1][i][diff]);
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

// https://oj.uz/problem/view/JOI16_skyscraper

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2760 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 3 ms 9308 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 5 ms 10072 KB Output is correct
10 Correct 2 ms 9308 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 110932 KB Output is correct
2 Correct 333 ms 487248 KB Output is correct
3 Correct 234 ms 477212 KB Output is correct
4 Correct 266 ms 487248 KB Output is correct
5 Correct 243 ms 487920 KB Output is correct
6 Correct 255 ms 487088 KB Output is correct
7 Correct 205 ms 473688 KB Output is correct
8 Correct 220 ms 476888 KB Output is correct
9 Correct 243 ms 483532 KB Output is correct
10 Correct 240 ms 483892 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2760 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 3 ms 9308 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 5 ms 10072 KB Output is correct
10 Correct 2 ms 9308 KB Output is correct
11 Correct 53 ms 110932 KB Output is correct
12 Correct 333 ms 487248 KB Output is correct
13 Correct 234 ms 477212 KB Output is correct
14 Correct 266 ms 487248 KB Output is correct
15 Correct 243 ms 487920 KB Output is correct
16 Correct 255 ms 487088 KB Output is correct
17 Correct 205 ms 473688 KB Output is correct
18 Correct 220 ms 476888 KB Output is correct
19 Correct 243 ms 483532 KB Output is correct
20 Correct 240 ms 483892 KB Output is correct
21 Runtime error 33 ms 37764 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -