Submission #200728

#	Time	Username	Problem	Language	Result	Execution time	Memory
200728		BThero	Boat (APIO16_boat)	C++17	0 / 100	2082 ms	636 KiB

boat

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e2 + 5;
const int MOD = (int)1e9 + 7;

int fact[MAXN], rev[MAXN];

int dp[MAXN][MAXN][MAXN];

vector<int> T;

pii arr[MAXN];

int n;

int addMod(int a, int b, int m = MOD) {
    a += b;

    if (m <= a) {
        a -= m;
    }
    
    return a;
}

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

int binPow(int a, int b, int m = MOD) {
    int ret = 1;

    while (b > 0) {
        if (b & 1) {
            ret = mulMod(ret, a, m);
        }

        a = mulMod(a, a, m);
        b >>= 1;
    }

    return ret;
}

void pre() {
    fact[0] = rev[0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        fact[i] = mulMod(fact[i - 1], i);
        rev[i] = binPow(fact[i], MOD - 2);
    }
}

int C(int n, int k) {
    if (n < 0 || k < 0 || k > n) {
        return 0;
    }

    int a = 1, b = 1;

    for (int i = n - k + 1; i <= k; ++i) {
        a = mulMod(a, i);
    }

    for (int i = 1; i <= k; ++i) {
        b = mulMod(b, i);
    }                        

    return mulMod(a, binPow(b, MOD - 2));
}

int f(int idx, int cnt) {
    int x = T[idx + 1] - T[idx];
    return C(x, cnt);
}

void solve() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &arr[i].fi, &arr[i].se);
        T.pb(arr[i].fi);
        T.pb(arr[i].se + 1);
    }

    T.pb(0);
    sort(all(T));
    T.resize(unique(all(T)) - T.begin());

    for (int i = 1; i <= n; ++i) {
        arr[i].fi = lower_bound(all(T), arr[i].fi) - T.begin();
        arr[i].se = lower_bound(all(T), arr[i].se + 1) - T.begin();
    }

    dp[0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int comp = 0; comp < T.size(); ++comp) {
            for (int j = 0; j <= n; ++j) {
                dp[i][comp][j] = dp[i - 1][comp][j];
            }
        }

        for (int comp = arr[i].fi; comp < arr[i].se; ++comp) {
            for (int prev = 0; prev < comp; ++prev) {
                for (int j = 0; j <= n; ++j) {
                    dp[i][comp][1] = addMod(dp[i][comp][1], mulMod(dp[i - 1][prev][j], f(prev, j)));
                }
            }

            for (int j = 1; j <= n; ++j) {
                dp[i][comp][j] = addMod(dp[i][comp][j], dp[i - 1][comp][j - 1]);
            }
        }
    }

    int ans = 0;

    for (int comp = 0; comp + 1 < T.size(); ++comp) {
        for (int cnt = 1; cnt <= n; ++cnt) {
            ans = addMod(ans, mulMod(dp[n][comp][cnt], f(comp, cnt)));
        }
    }                

    printf("%d\n", ans);
}

int main() {
    int tt = 1;

    pre();

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:118:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int comp = 0; comp < T.size(); ++comp) {
                            ~~~~~^~~~~~~~~~
boat.cpp:139:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int comp = 0; comp + 1 < T.size(); ++comp) {
                        ~~~~~~~~~^~~~~~~~~~
boat.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arr[i].fi, &arr[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42