oj.uz

Submission #96525

# Submission time Handle Problem Language Result Execution time Memory
96525 2019-02-10T06:26:47 Z tichuot97 Skyscraper (JOI16_skyscraper) C++14
15 / 100
 110 ms 143880 KB 
#include <iostream>
#include <algorithm>
#include <cstring>

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;
    //cout << i << " " << cc << " " << s << " " << e << endl;
    if (f[i][cc][s][e] != -1) return f[i][cc][s][e];
    int tmp = 0;
    int up = a[i] - a[i - 1];
    int cost = s + (2 * cc - e) * up;
    // ** 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 = (tmp + 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;
}

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:55: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 143776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 143860 KB Output is correct
2 Correct 106 ms 143880 KB Output is correct
3 Correct 110 ms 143736 KB Output is correct
4 Correct 96 ms 143864 KB Output is correct
5 Correct 96 ms 143736 KB Output is correct
6 Correct 98 ms 143864 KB Output is correct
7 Correct 108 ms 143840 KB Output is correct
8 Correct 109 ms 143736 KB Output is correct
9 Correct 100 ms 143780 KB Output is correct
10 Correct 95 ms 143864 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 143776 KB Output isn't correct
2 Halted 0 ms 0 KB -