oj.uz

Submission #306916

# Submission time Handle Problem Language Result Execution time Memory
306916 2020-09-26T14:18:04 Z jungsnow Skyscraper (JOI16_skyscraper) C++14
0 / 100
 2000 ms 512 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 101;
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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 424 KB Output is correct
2 Correct 525 ms 428 KB Output is correct
3 Execution timed out 2058 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -