Submission #200738

#	Time	Username	Problem	Language	Result	Execution time	Memory
200738		BThero	Boat (APIO16_boat)	C++17	27 / 100	39 ms	17036 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)2e2 + 5;
const int MOD = (int)1e9 + 7;

int fact[MAXN], rev[MAXN];

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

int mem[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 <= n; ++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();
    }

    for (int i = 0; i + 1 < T.size(); ++i) {
        for (int j = 0; j <= n; ++j) {
            mem[i][j] = f(i, j);
        }
    }    

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

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

        int p = 0, w = 0;

        for (int c = arr[i].fi; c < arr[i].se; ++c) {
            for (int cnt = 1; cnt <= n; ++cnt) {
                dp[i][c][cnt] = addMod(dp[i][c][cnt], dp[i - 1][c][cnt - 1]);                                                                
            }

            while (p < c) {
                for (int cnt = 0; cnt <= n; ++cnt) {
                    w = addMod(w, mulMod(dp[i - 1][p][cnt], mem[p][cnt]));
                }

                ++p;
            }

            dp[i][c][1] = addMod(dp[i][c][1], w);
        }
    }

    int ans = 0;

    for (int c = 0; c + 1 < T.size(); ++c) {
        for (int cnt = 1; cnt <= n; ++cnt) {
            ans = addMod(ans, mulMod(dp[n][c][cnt], mem[c][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:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < T.size(); ++i) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int c = 0; c < T.size(); ++c) {
                         ~~^~~~~~~~~~
boat.cpp:153:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int c = 0; c + 1 < T.size(); ++c) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:103: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: 27 / 27
• Subtask 4: 0 / 42