oj.uz

Submission #434963

# Submission time Handle Problem Language Result Execution time Memory
434963 2021-06-22T14:29:10 Z Lam_lai_cuoc_doi Boat (APIO16_boat) C++17
9 / 100
 1104 ms 8260 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<int, int> s[N];
vector<int> block;

void Read()
{
    scanf("%d", &n); //cin >> n;

    block.reserve(n * 2);

    for (int i = 1; i <= n; ++i)
    {
        //cin >> s[i].first >> s[i].second;
        scanf("%d%d", &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] * i % mod;

    ll tmp = Pow(inv[n], mod - 2);

    for (int i = n; i; --i)
    {
        inv[i] = tmp * inv[i - 1] % mod;
        (tmp *= i) %= 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 * inv[t + 1] % mod * (block[i] - block[i - 1] - (t + 1) + 1) % mod;

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

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

            d[i][j] %= 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;
                    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
                }

            dp[i][j] %= mod;
        }
    }

    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();
    }
}

Compilation message

boat.cpp: In function 'void Read()':
boat.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d", &n); //cin >> n;
      |     ~~~~~^~~~~~~~~~
boat.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d", &s[i].first, &s[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 8076 KB Output is correct
2 Correct 1092 ms 8180 KB Output is correct
3 Correct 1099 ms 8260 KB Output is correct
4 Correct 1090 ms 8176 KB Output is correct
5 Correct 1088 ms 8056 KB Output is correct
6 Correct 1018 ms 8092 KB Output is correct
7 Correct 982 ms 8220 KB Output is correct
8 Correct 1000 ms 8140 KB Output is correct
9 Correct 1000 ms 8208 KB Output is correct
10 Correct 1002 ms 8152 KB Output is correct
11 Correct 990 ms 8208 KB Output is correct
12 Correct 1014 ms 8212 KB Output is correct
13 Correct 1004 ms 8240 KB Output is correct
14 Correct 993 ms 8252 KB Output is correct
15 Correct 1004 ms 8164 KB Output is correct
16 Correct 197 ms 3652 KB Output is correct
17 Correct 217 ms 3824 KB Output is correct
18 Correct 210 ms 3776 KB Output is correct
19 Correct 213 ms 3768 KB Output is correct
20 Correct 207 ms 3728 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 8076 KB Output is correct
2 Correct 1092 ms 8180 KB Output is correct
3 Correct 1099 ms 8260 KB Output is correct
4 Correct 1090 ms 8176 KB Output is correct
5 Correct 1088 ms 8056 KB Output is correct
6 Correct 1018 ms 8092 KB Output is correct
7 Correct 982 ms 8220 KB Output is correct
8 Correct 1000 ms 8140 KB Output is correct
9 Correct 1000 ms 8208 KB Output is correct
10 Correct 1002 ms 8152 KB Output is correct
11 Correct 990 ms 8208 KB Output is correct
12 Correct 1014 ms 8212 KB Output is correct
13 Correct 1004 ms 8240 KB Output is correct
14 Correct 993 ms 8252 KB Output is correct
15 Correct 1004 ms 8164 KB Output is correct
16 Correct 197 ms 3652 KB Output is correct
17 Correct 217 ms 3824 KB Output is correct
18 Correct 210 ms 3776 KB Output is correct
19 Correct 213 ms 3768 KB Output is correct
20 Correct 207 ms 3728 KB Output is correct
21 Incorrect 349 ms 7784 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 8076 KB Output is correct
2 Correct 1092 ms 8180 KB Output is correct
3 Correct 1099 ms 8260 KB Output is correct
4 Correct 1090 ms 8176 KB Output is correct
5 Correct 1088 ms 8056 KB Output is correct
6 Correct 1018 ms 8092 KB Output is correct
7 Correct 982 ms 8220 KB Output is correct
8 Correct 1000 ms 8140 KB Output is correct
9 Correct 1000 ms 8208 KB Output is correct
10 Correct 1002 ms 8152 KB Output is correct
11 Correct 990 ms 8208 KB Output is correct
12 Correct 1014 ms 8212 KB Output is correct
13 Correct 1004 ms 8240 KB Output is correct
14 Correct 993 ms 8252 KB Output is correct
15 Correct 1004 ms 8164 KB Output is correct
16 Correct 197 ms 3652 KB Output is correct
17 Correct 217 ms 3824 KB Output is correct
18 Correct 210 ms 3776 KB Output is correct
19 Correct 213 ms 3768 KB Output is correct
20 Correct 207 ms 3728 KB Output is correct
21 Incorrect 349 ms 7784 KB Output isn't correct
22 Halted 0 ms 0 KB -