제출 #1345003

#제출 시각아이디문제언어결과실행 시간메모리
1345003adscodingBoat (APIO16_boat)C++20
100 / 100
682 ms5428 KiB
#include <bits/stdc++.h>
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define fi first
#define se second
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define FORLL(i, a, b) for (ll i = a, _b = b; i <= _b; ++i)
#define FORDLL(i, a, b) for (ll i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void __print_one(const char *&s, const T &x)
{
    while (*s == ' ') ++s;
    const char *p = s;
    int bal = 0;
    while (*s)
    {
        if (*s == '(') ++bal;
        else if (*s == ')') --bal;
        else if (*s == ',' && bal == 0) break;
        ++s;
    }

    cerr.write(p, s - p) << " = " << x;
    if (*s == ',')
    {
        cerr << "  ,  ";
        ++s;
    }
}

template<typename... Args>
void debug(const char *s, Args... args)
{
    cerr << "[  ";
     int dummy[] = {0, (__print_one(s, args), 0)...};
    (void)dummy;
    cerr << "  ]\n\n";
}

template<class X>
bool maximize(X &a, X b)
{
    if (b > a)
    {
        a = b;
        return true;
    }
    return false;
}

template<class X>
bool minimize(X &a, X b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

// -----------------------------------------------------------------------------------------

constexpr int maxn = 505, MOD = 1e9 + 7;
int n, A[maxn], B[maxn], dp[maxn][2 * maxn + 5], F[2 * maxn + 5][maxn], inv[maxn], C[maxn][maxn], fact[maxn];
vector<int> vecPoint;
vector<pii> intervals;

// -----------------------------------------------------------------------------------------

void readInput()
{
    cin >> n;
    FOR(i, 1, n)
    {
        cin >> A[i] >> B[i];
        vecPoint.push_back(A[i]);
        vecPoint.push_back(B[i] + 1);
    }
}

int add(int a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int mul(int a, int b)
{
    a = (1ll * a * b) % MOD;
    return a;
}

int binpow(int a, int b)
{
    int res = 1;
    for (; b; b >>= 1, a = mul(a, a))
        if (b & 1) res = mul(res, a);
    return res;
}

void preprocess()
{
    fact[0] = 1;
    FOR(i, 1, n)
        fact[i] = mul(fact[i - 1], i);
    inv[n] = binpow(fact[n], MOD - 2);
    FORD(i, n - 1, 0)
        inv[i] = mul(inv[i + 1], i + 1);

    uni(vecPoint);
    intervals.push_back({-int(1e9), -int(1e9)});
    FOR(i, 0, SZ(vecPoint) - 2)
        intervals.push_back({vecPoint[i], vecPoint[i + 1] - 1});

//    for (pii p : intervals)
//        dbg(p.fi, p.se);

    FOR(i, 0, n)
    {
        C[i][0] = C[i][i] = 1;
        FOR(j, 1, i - 1)
            C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }

    FOR(i, 1, SZ(intervals) - 1)
    {
        int len = intervals[i].se - intervals[i].fi + 1;
        FORD(CNT, n, 1)
        {
            int curC = 1;
            FOR(k, 1, min(CNT, len))
            {
                curC = mul(curC, len - k + 1);
                F[i][CNT] = add(F[i][CNT], mul(mul(curC, inv[k]) , C[CNT - 1][k - 1]));
            }
        }
    }
}

bool cover(int i, int j)
{
    return intervals[j].fi >= A[i] && intervals[j].se <= B[i];
}

void solve()
{
    dp[0][0] = 1;
    FOR(i, 1, SZ(intervals) - 1)
        dp[0][i] = 1;
    int res = 0;
    FOR(i, 1, n)
    {
        FOR(j, 1, SZ(intervals) - 1)
        {
            if (cover(i, j))
            {
                int CNT = 1;
                FORD(k, i - 1, 0)
                {
                    dp[i][j] = add(dp[i][j], mul(dp[k][j - 1], F[j][CNT]));
                    CNT += cover(k, j);
                }
            }
//            dbg(i, j, dp[i][j]);
            dp[i][j] = add(dp[i][j], dp[i][j - 1]);
        }
        res = add(res, dp[i][SZ(intervals) - 1]);
    }

    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    readInput();
    preprocess();
    solve();
    return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...