Submission #294033

#	Time	Username	Problem	Language	Result	Execution time	Memory
294033		Shafin666	Boat (APIO16_boat)	C++14	100 / 100	609 ms	8440 KiB

boat

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const ll mod = 1e9+7, maxn = 1e3+10;
ll l[maxn], r[maxn];
ll dp[maxn][maxn], sum[maxn][maxn];
ll ncr[maxn][maxn], inv[maxn];
vector<pii> edit;
vector<ll> v;

ll bigmod(ll a, ll b) {
    if(b == 0) return 1;
    ll x = bigmod(a, b/2);
    x = (x * x) % mod;
    if(b & 1) x = (x * a) % mod;
    return x;
}

int main() 
{
    ll n; cin >> n;
    for(ll i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        v.pb(l[i]); v.pb(r[i]+1);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    edit.pb({0, 0});
    for(ll i = 0; i < (ll)v.size()-1; i++) {
        edit.pb({v[i], v[i+1]-1});
    }
    ll m = edit.size() - 1;

    for(ll i = 1; i <= n; i++) inv[i] = bigmod(i, mod-2);

    dp[0][0] = 1;
    for(ll i = 0; i <= m; i++) sum[0][i] = 1;

    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= m; j++) {

            ll L = edit[j].second - edit[j].first + 1;
            ll cnt = 1, mul = L;

            if(!(l[i] <= edit[j].first && r[i] >= edit[j].second)) continue;

            for(ll k = i-1; k >= 0; k--) {
                dp[i][j] = (dp[i][j] + mul * sum[k][j-1]) % mod;
                if(l[k] <= edit[j].first && r[k] >= edit[j].second) {
                    cnt++;
                    mul = (mul * (L + cnt - 1)) % mod;
                    mul = (mul * inv[cnt]) % mod;
                }
            }
        }

        for(ll j = 1; j <= m; j++)
            sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
    }

    ll ans = 0;
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= m; j++)
            ans = (ans + dp[i][j]) % mod;
    }

    cout << ans << endl;

    return 0;
}

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