Submission #318363

#	Time	Username	Problem	Language	Result	Execution time	Memory
318363		a14789654	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	381 ms	180996 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7, MAXN = 107, MAXL = 1007;

int a[MAXN], f[MAXN][MAXL][2][MAXN][2], n, l;

void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

int calc(int i, int curl, int kl, int k, int kr)
{
    /// kl = 1 if there is a segment connected to the left border, 0 otherwise
    /// kr = 1 if there is a segment connected to the right border, 0 otherwise
    /// k is the number of segments in the middle
    int nxtl = curl;
    if (i) nxtl += (kl + kr + 2 * k) * (a[i] - a[i - 1]); ///Add penalty
    if (nxtl > l) return 0;
    if (k < 0) return 0;
    if (i == n - 1) return !k && (kl || kr);
    if (f[i][curl][kl][k][kr] != - 1) return f[i][curl][kl][k][kr];

    int ans = 0;
    add(ans, calc(i + 1, nxtl, 1, k, kr)); ///Connect to left segmenet
    add(ans, 1LL * calc(i + 1, nxtl, 1, k - 1, kr) * k % MOD); ///Connect to left segment and join to a middle segment

    add(ans, calc(i + 1, nxtl, kl, k, 1)); ///Connect to right segment
    add(ans, 1LL * calc(i + 1, nxtl, kl, k - 1, 1) * k % MOD); /// Connect to right segment and join to a middle segment

    add(ans, calc(i + 1, nxtl, kl, k + 1, kr)); ///Create new segment
    add(ans, 1LL * calc(i + 1, nxtl, kl, k, kr) * k * 2 % MOD); ///Connect to a middle segment
    add(ans, 1LL * k * (k - 1) * calc(i + 1, nxtl, kl, k - 1, kr) % MOD); ///Use to join two middle segments
    return f[i][curl][kl][k][kr] = ans;
}

int main()
{
    if (fopen("tst.inp", "r"))
    {
        freopen("tst.inp", "r", stdin);
        freopen("tst.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> l;
    if (n == 1) return cout << 1, 0;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    memset(f, - 1, sizeof(f));
    cout << calc(0, 0, 0, 0, 0);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         freopen("tst.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   45 |         freopen("tst.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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