oj.uz

Submission #318362

# Submission time Handle Problem Language Result Execution time Memory
318362 2020-11-01T12:49:10 Z a14789654 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 94 ms 180836 KB 
#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;
    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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 180836 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 90 ms 180836 KB Output is correct
2 Correct 90 ms 180836 KB Output is correct
3 Correct 93 ms 180836 KB Output is correct
4 Correct 90 ms 180836 KB Output is correct
5 Correct 94 ms 180836 KB Output is correct
6 Correct 91 ms 180836 KB Output is correct
7 Correct 93 ms 180716 KB Output is correct
8 Correct 92 ms 180836 KB Output is correct
9 Correct 92 ms 180836 KB Output is correct
10 Correct 91 ms 180836 KB Output is correct

Subtask #3
0 / 80.0

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