Submission #200866

#	Time	Username	Problem	Language	Result	Execution time	Memory
200866		BThero	Boat (APIO16_boat)	C++17	100 / 100	789 ms	8440 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)1e3 + 5;
const int MOD = (int)1e9 + 7;

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

vector<int> T;

pii arr[MAXN];

int rev[MAXN];

int n;

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

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

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

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

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

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

    return ret;
}

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 = 1; i < MAXN; ++i) {
        rev[i] = binPow(i, MOD - 2);
    } 

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

    for (int i = 1; i <= n; ++i) {
        int p = 0, w = 0;

        for (int c = arr[i].fi; c < arr[i].se; ++c) {
            int lim = T[c + 1] - T[c];

            for (int cnt = 1; cnt <= i; ++cnt) {
                int tmp = dp[0][c][cnt - 1];
                mulMod(tmp, max(0, lim - cnt + 1));
                mulMod(tmp, rev[cnt]);
                addMod(dp[1][c][cnt], tmp);                                                                
            }

            while (p < c) {
                for (int cnt = 0; cnt <= i; ++cnt) {
                    int tmp = dp[0][p][cnt];
                    addMod(w, tmp);
                }

                ++p;
            }

            int tmp = w;
            mulMod(tmp, lim);
            addMod(dp[1][c][1], tmp);
        }

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

    int ans = 0;

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

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

int main() {
    int tt = 1;

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

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int c = 0; c < T.size(); ++c) {
                         ~~^~~~~~~~~~
boat.cpp:124:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int c = 1; c + 1 < T.size(); ++c) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:67: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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42