Submission #306918

#	Time	Username	Problem	Language	Result	Execution time	Memory
306918		jungsnow	Skyscraper (JOI16_skyscraper)	C++14	5 / 100	2082 ms	4344 KiB

skyscraper

#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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80