oj.uz

Submission #434949

# Submission time Handle Problem Language Result Execution time Memory
434949 2021-06-22T13:35:24 Z Lam_lai_cuoc_doi Boat (APIO16_boat) C++17
9 / 100
 1158 ms 8372 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 8236 KB Output is correct
2 Correct 1156 ms 8160 KB Output is correct
3 Correct 1140 ms 8320 KB Output is correct
4 Correct 1137 ms 8192 KB Output is correct
5 Correct 1158 ms 8172 KB Output is correct
6 Correct 1045 ms 8216 KB Output is correct
7 Correct 1025 ms 8312 KB Output is correct
8 Correct 1055 ms 8292 KB Output is correct
9 Correct 1043 ms 8080 KB Output is correct
10 Correct 1020 ms 8372 KB Output is correct
11 Correct 1025 ms 8192 KB Output is correct
12 Correct 1040 ms 8160 KB Output is correct
13 Correct 1070 ms 8156 KB Output is correct
14 Correct 1074 ms 8340 KB Output is correct
15 Correct 1031 ms 8184 KB Output is correct
16 Correct 208 ms 3652 KB Output is correct
17 Correct 229 ms 3792 KB Output is correct
18 Correct 213 ms 3652 KB Output is correct
19 Correct 226 ms 3788 KB Output is correct
20 Correct 216 ms 3796 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 8236 KB Output is correct
2 Correct 1156 ms 8160 KB Output is correct
3 Correct 1140 ms 8320 KB Output is correct
4 Correct 1137 ms 8192 KB Output is correct
5 Correct 1158 ms 8172 KB Output is correct
6 Correct 1045 ms 8216 KB Output is correct
7 Correct 1025 ms 8312 KB Output is correct
8 Correct 1055 ms 8292 KB Output is correct
9 Correct 1043 ms 8080 KB Output is correct
10 Correct 1020 ms 8372 KB Output is correct
11 Correct 1025 ms 8192 KB Output is correct
12 Correct 1040 ms 8160 KB Output is correct
13 Correct 1070 ms 8156 KB Output is correct
14 Correct 1074 ms 8340 KB Output is correct
15 Correct 1031 ms 8184 KB Output is correct
16 Correct 208 ms 3652 KB Output is correct
17 Correct 229 ms 3792 KB Output is correct
18 Correct 213 ms 3652 KB Output is correct
19 Correct 226 ms 3788 KB Output is correct
20 Correct 216 ms 3796 KB Output is correct
21 Incorrect 420 ms 7900 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 8236 KB Output is correct
2 Correct 1156 ms 8160 KB Output is correct
3 Correct 1140 ms 8320 KB Output is correct
4 Correct 1137 ms 8192 KB Output is correct
5 Correct 1158 ms 8172 KB Output is correct
6 Correct 1045 ms 8216 KB Output is correct
7 Correct 1025 ms 8312 KB Output is correct
8 Correct 1055 ms 8292 KB Output is correct
9 Correct 1043 ms 8080 KB Output is correct
10 Correct 1020 ms 8372 KB Output is correct
11 Correct 1025 ms 8192 KB Output is correct
12 Correct 1040 ms 8160 KB Output is correct
13 Correct 1070 ms 8156 KB Output is correct
14 Correct 1074 ms 8340 KB Output is correct
15 Correct 1031 ms 8184 KB Output is correct
16 Correct 208 ms 3652 KB Output is correct
17 Correct 229 ms 3792 KB Output is correct
18 Correct 213 ms 3652 KB Output is correct
19 Correct 226 ms 3788 KB Output is correct
20 Correct 216 ms 3796 KB Output is correct
21 Incorrect 420 ms 7900 KB Output isn't correct
22 Halted 0 ms 0 KB -