Submission #96537

#	Time	Username	Problem	Language	Result	Execution time	Memory
96537		tichuot97	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	255 ms	143868 KiB

skyscraper

#include <iostream>
#include <algorithm>
#include <cstring>
#include <time.h>
#include <set>

using namespace std;

const int maxN = 110, maxS = 1010, oo = 23041997, modP = 1e9 + 7;

int f[maxN][maxN][maxS][3], n, a[maxN], l;

int dp(int i, int cc, int s, int e) {
    if (s > l) return 0;
    if (i > n) return cc == 1 && e == 2;
    if (f[i][cc][s][e] != -1) return f[i][cc][s][e];
    int tmp = 0;
    int cost = s + (2 * cc - e) * (a[i] - a[i - 1]);
    // ** Add new component **
    // 1. Endpoints:
    if (e < 2) {
        tmp = (1ll * tmp + 1ll * dp(i + 1, cc + 1, cost, e + 1) * (2 - e)) % modP;
        // Merge new one with sth else immediately:
        if (i == n && cc == 1 && e == 1)
            tmp = (1ll * tmp + 1ll * dp(i + 1, cc, cost, e + 1)) % modP;
        else if (cc - e)
            tmp = (1ll * tmp + 1ll * dp(i + 1, cc, cost, e + 1) * (2 - e) * (cc - e)) % modP;
    }
    // 2. Middle:
    tmp = (tmp + dp(i + 1, cc + 1, cost, e)) % modP;
    // ** Add to existing component **
    // 1. Endpoints:
    if (e) tmp = (1ll * tmp + 1ll * dp(i + 1, cc, cost, e) * e) % modP;
    // 2. Middle:
    //if (i == 3 && cc == 2 && s == 1 && e == 1) cout << "OK " << tmp << endl;
    if (cc - e) tmp = (1ll * tmp + 1ll * dp(i + 1, cc, cost, e) * (2 * (cc - e))) % modP;
    //if (i == 3 && cc == 2 && s == 1 && e == 1) cout << "OK " << tmp << endl;
    // ** Merge existing components **
    // 1. Endpoint with middle:
    if (e && cc - e)
        tmp = (1ll * tmp + 1ll * dp(i + 1, cc - 1, cost, e) * e * (cc - e)) % modP;
    // 2. Middle with middle:
    if (cc - e >= 2)
        tmp = (1ll * tmp + 1ll * dp(i + 1, cc - 1, cost, e) * (cc - e) * (cc - e - 1)) % modP;
    // 3. Endpoint with endpoint:
    if (e == 2 && cc == 2 && i == n)
        tmp = (1ll * tmp + 1ll * dp(i + 1, cc - 1, cost, e)) % modP;
    //cout << i << " " << cc << " " << s << " " << e << endl;
    //cout << tmp << endl;
    return f[i][cc][s][e] = tmp;
}

void randomize_input() {
    srand(time(NULL));
    n = rand() % 100 + 1;
    l = rand() % 1000 + 1;
    cout << n << " " << l << endl;
    set < int > mset;
    for (int i = 1; i <= n; ++i) {
        a[i] = rand() % 200 + 1;
        while (mset.count(a[i])) a[i] = rand() % 100 + 1;
        mset.insert(a[i]);
        printf("%d ", a[i]);
    }
    cout << endl;
}

int main() {
    cin >> n >> l;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    //randomize_input();
    if (n == 1) { cout << 1; return 0; }
    sort(a + 1, a + n + 1);
    memset(f, 255, sizeof(f));
    cout << dp(1, 0, 0, 0);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:70:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80