제출 #465071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465071		arminatarod	Boat (APIO16_boat)	C++17	100 / 100	1851 ms	8352 KiB

boat

#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 *= inv[t + 1] * (block[i] - block[i - 1] - (t + 1) + 1) % mod) %= mod;
 
                d[i][j] += c1 * c2 % mod;
 
                (c1 *= inv[t + 1] * (j - 1 - (t + 1) + 1) % mod) %= 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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42