Submission #200761

#	Time	Username	Problem	Language	Result	Execution time	Memory
200761		BThero	Boat (APIO16_boat)	C++17	100 / 100	727 ms	12408 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];

int mem[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 = 0; i <= n; ++i) {
        rev[i] = binPow(i, MOD - 2);        
    }

    for (int i = 0; i + 1 < T.size(); ++i) {
        int x = T[i + 1] - T[i];
        mem[i][0] = 1;

        for (int j = 1; j <= n; ++j) {
            if (j > x) {
                mem[i][j] = 0;
                continue;
            }

            int tmp = mem[i][j - 1];
            mulMod(tmp, x - j + 1);
            mulMod(tmp, rev[j]);
            mem[i][j] = tmp;
        }                                                                                    
    }    

    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) {
            for (int cnt = 1; cnt <= i; ++cnt) {
                addMod(dp[1][c][cnt], dp[0][c][cnt - 1]);                                                                
            }

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

                ++p;
            }

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

        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 = 0; c + 1 < T.size(); ++c) {
        for (int cnt = 1; cnt <= n; ++cnt) {
            int tmp = dp[0][c][cnt];
            mulMod(tmp, mem[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:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < T.size(); ++i) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int c = 0; c < T.size(); ++c) {
                         ~~^~~~~~~~~~
boat.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int c = 0; c + 1 < T.size(); ++c) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:69: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