oj.uz

Submission #306918

# Submission time Handle Problem Language Result Execution time Memory
306918 2020-09-26T14:19:52 Z jungsnow Skyscraper (JOI16_skyscraper) C++14
5 / 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();
    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]);
                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 3 ms 4224 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 15 ms 4224 KB Output is correct
6 Correct 15 ms 4224 KB Output is correct
7 Correct 15 ms 4224 KB Output is correct
8 Correct 17 ms 4224 KB Output is correct
9 Correct 17 ms 4224 KB Output is correct
10 Correct 15 ms 4224 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 4224 KB Output is correct
2 Correct 1139 ms 4344 KB Output is correct
3 Execution timed out 2082 ms 4224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 3 ms 4224 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 15 ms 4224 KB Output is correct
6 Correct 15 ms 4224 KB Output is correct
7 Correct 15 ms 4224 KB Output is correct
8 Correct 17 ms 4224 KB Output is correct
9 Correct 17 ms 4224 KB Output is correct
10 Correct 15 ms 4224 KB Output is correct
11 Correct 408 ms 4224 KB Output is correct
12 Correct 1139 ms 4344 KB Output is correct
13 Execution timed out 2082 ms 4224 KB Time limit exceeded
14 Halted 0 ms 0 KB -