Submission #512993

#	Time	Username	Problem	Language	Result	Execution time	Memory
512993		TheScrasse	Boat (APIO16_boat)	C++17	100 / 100	1869 ms	24360 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 1000000007
#define maxn 2010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
ll ps1[maxn][maxn], ps2[maxn][maxn], nv[maxn], l, r, dp, ln;
vector<ll> cm;
map<ll, ll> dc;

ll fxp(ll b, ll e) {
    ll r;
    if (e == 0) return 1;
    if (e % 2) {
        r = fxp(b, e - 1); return (b * r) % mod;
    } else {
        r = fxp(b, e / 2); return (r * r) % mod;
    }
}

ll inv(ll x) {
    return fxp(x, mod - 2);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    for (i = 1; i < maxn; i++) nv[i] = inv(i);

    cin >> n; cm.pb(-1); cm.pb(0);
    for (i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        cm.pb(a[i] - 1); cm.pb(a[i]); cm.pb(b[i] - 1); cm.pb(b[i]);
    }

    sort(cm.begin(), cm.end());
    cm.resize(unique(cm.begin(), cm.end()) - cm.begin());

    for (i = 0; i < cm.size(); i++) dc[cm[i]] = i;
    for (i = 0; i <= n; i++) {
        a[i] = dc[a[i]]; b[i] = dc[b[i]];
    }

    // for (i = 0; i <= n; i++) cout << a[i] _ b[i] << nl;

    for (i = 0; i <= n; i++) {
        l = a[i]; r = b[i];
        for (j = 0; j <= 4 * n + 1; j++) {
            if (j >= l && j <= r) {
                ln = cm[j] - cm[j - 1];
                for (k = n; k >= 1; k--) {
                    if (i == 0) {
                        if (j == 1 && k == 1) dp = 1;
                    } else {
                        if (k == 1) dp = (ps1[i - 1][j - 1] * ln) % mod;
                        else dp = (((ps2[j][k - 1] * (ln - k + 1)) % mod) * nv[k]) % mod;
                    }
                    ps1[i][j] = (ps1[i][j] + dp) % mod;
                    ps2[j][k] = (ps2[j][k] + dp) % mod;
                    // if (dp != 0) cout << i _ j _ k _ dp << nl;
                }
            } else {
                dp = 0;
            }
            if (i >= 1) ps1[i][j] += ps1[i - 1][j];
            if (j >= 1) ps1[i][j] += ps1[i][j - 1];
            if (i >= 1 && j >= 1) ps1[i][j] -= ps1[i - 1][j - 1];
            ps1[i][j] = (ps1[i][j] + mod) % mod;
        }
    }

    cout << (ps1[n][4 * n + 1] + mod - 1) % mod << nl;

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:53:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (i = 0; i < cm.size(); i++) dc[cm[i]] = i;
      |                 ~~^~~~~~~~~~~

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