oj.uz

Submission #434948

# Submission time Handle Problem Language Result Execution time Memory
434948 2021-06-22T13:34:42 Z Lam_lai_cuoc_doi Boat (APIO16_boat) C++17
0 / 100
 1220 ms 11976 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 5e2 + 2;
constexpr ll mod = 1e9 + 7;

/* https://codeforces.com/blog/entry/57324?#comment-409800 */

int n;

/// dp[i][j]: choose i first elements in j first blocks
ll dp[N][N * 2], d[N * 2][N], inv[N];

pair<ll, ll> s[N];
vector<int> block;

void Read()
{
    cin >> n;

    block.reserve(n * 2);

    for (int i = 1; i <= n; ++i)
    {
        cin >> s[i].first >> s[i].second;
        block.emplace_back(s[i].first - 1);
        block.emplace_back(s[i].second);
    }

    sort(block.begin(), block.end());
    block.resize(unique(block.begin(), block.end()) - block.begin());
}

ll Pow(ll a, ll b)
{
    ll ans(1);

    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }

    return ans;
}

void Solve()
{
    inv[0] = 1;
    for (int i = 1; i <= n; ++i)
        inv[i] = inv[i - 1] * Pow(i, mod - 2) % mod;

    /// Pre-calculate d[], I'll define d[] below

    for (int i = 1; i < (int)block.size(); ++i)
    {
        d[i][0] = 1;
        for (int j = 1; j <= n; ++j)
        {
            ll c1(1), c2(1);
            for (int t = 0; t < j && t + 1 <= block[i] - block[i - 1]; ++t)
            {
                c2 = c2 * ((block[i] - block[i - 1] - (t + 1) + 1) % mod) % mod * inv[t + 1] % mod;

                (d[i][j] += c1 * c2) %= mod;

                c1 = c1 * (j - 1 - (t + 1) + 1) % mod * inv[t + 1] % mod;
            }
        }
    }

    for (int i = 0; i < (int)block.size(); ++i)
        dp[0][i] = 1;

    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 1;
        for (int j = 1; j < (int)block.size(); ++j)
        {
            /// no element in j block
            dp[i][j] = dp[i][j - 1];

            /// there're some elements in j block
            for (int t = i, cnt(0); t; --t)
                if (s[t].first <= block[j - 1] + 1 && s[t].second >= block[j])
                {
                    ++cnt;
                    //cout << cnt << "+" << t << "-";
                    (dp[i][j] += dp[t - 1][j - 1] * d[j][cnt]) %= mod;
                    /// d[j][i] : number of ways to make array that have less or equal i element only from block j
                    /// to prevent overlap counting, we need to change sthg about definition
                }

            cout << dp[i][j] << " ";
        }

        cout << "\n";
    }

    cout << dp[n][block.size() - 1] - 1;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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