oj.uz

Submission #306928

# Submission time Handle Problem Language Result Execution time Memory
306928 2020-09-26T14:31:32 Z jungsnow Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 4344 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1001;
const int mod = 1e9 + 7;

int n, L, a[N], ans;
int half, cn[N][N];
bool v[N];
vector <int> A, B;

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

void process() {
    memset(cn, 0, sizeof cn);
    A.clear();
    B.clear();
    for (int i = 1; i <= n; ++i)
        if (v[i]) A.push_back(i);
        else B.push_back(i);
    do {
        bool ok = 1;
        int sum = 0;
        for (int i = 1; i < half; ++i) {
            int tm = abs(a[ A[i] ] - a[ A[i - 1] ]);
            sum += tm;
            if (sum > L) {
                ok = 0;
                break;
            }
        }
        if (ok) cn[sum][ A[half - 1] ]++;
    } while (next_permutation(A.begin(), A.end()));
    int m = (int)B.size();
    for (int i = 1; i <= n; ++i) if (v[i]) {
        for (int j = 1; j <= L; ++j) {
            add(cn[j][i], cn[j - 1][i]);
        }
    }
    do {
        bool ok = 1;
        int sum = 0;
        for (int i = 1; i < m; ++i) {
            int tm = abs(a[ B[i] ] - a[ B[i - 1] ]);
            sum += tm;
            if (sum > L) {
                ok = 0;
                break;
            }
        }

        if (ok) {
            for (int i = 1; i <= n; ++i) if (v[i]) {
                int tm = abs(a[ B[0] ] - a[i]);
                if (L - tm - sum >= 0)
                    add(ans, cn[ L - tm - sum ][i]);
//                for (int j = 0; j + tm + sum <= L; ++j) {
//                    add(ans, cn[j][i]);
//                }
            }
        }
    } while (next_permutation(B.begin(), B.end()));
}

void go(int id, int num) {
    if (num > half) {
        process();
        return;
    }
    int need = half - num;
    for (int i = id; i + need <= n; ++i) {
        v[i] = 1;
        go(i + 1, num + 1);
        v[i] = 0;
    }
}

int main() {
//    freopen("cc.inp", "r", stdin);
//    freopen("cc.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> L;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    half = n / 2;
    go(1, 1);
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 4 ms 4224 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 15 ms 4224 KB Output is correct
6 Correct 16 ms 4224 KB Output is correct
7 Correct 15 ms 4224 KB Output is correct
8 Correct 15 ms 4224 KB Output is correct
9 Correct 15 ms 4224 KB Output is correct
10 Correct 16 ms 4224 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 4224 KB Output is correct
2 Correct 1141 ms 4344 KB Output is correct
3 Correct 1932 ms 4344 KB Output is correct
4 Correct 1151 ms 4344 KB Output is correct
5 Correct 1057 ms 4344 KB Output is correct
6 Correct 1564 ms 4304 KB Output is correct
7 Correct 1117 ms 4224 KB Output is correct
8 Correct 1927 ms 4344 KB Output is correct
9 Correct 1944 ms 4344 KB Output is correct
10 Correct 1152 ms 4308 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 4 ms 4224 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 15 ms 4224 KB Output is correct
6 Correct 16 ms 4224 KB Output is correct
7 Correct 15 ms 4224 KB Output is correct
8 Correct 15 ms 4224 KB Output is correct
9 Correct 15 ms 4224 KB Output is correct
10 Correct 16 ms 4224 KB Output is correct
11 Correct 208 ms 4224 KB Output is correct
12 Correct 1141 ms 4344 KB Output is correct
13 Correct 1932 ms 4344 KB Output is correct
14 Correct 1151 ms 4344 KB Output is correct
15 Correct 1057 ms 4344 KB Output is correct
16 Correct 1564 ms 4304 KB Output is correct
17 Correct 1117 ms 4224 KB Output is correct
18 Correct 1927 ms 4344 KB Output is correct
19 Correct 1944 ms 4344 KB Output is correct
20 Correct 1152 ms 4308 KB Output is correct
21 Execution timed out 2088 ms 4224 KB Time limit exceeded
22 Halted 0 ms 0 KB -