Submission #545636

#	Time	Username	Problem	Language	Result	Execution time	Memory
545636		flashhh	Boat (APIO16_boat)	C++14	100 / 100	481 ms	16244 KiB

boat

#include <bits/stdc++.h>
#define ll long long
#define N 505
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back

const int oo = 1e9 + 7;

using namespace std;

int n,m;
pii a[N],b[N*4];
ll res,inv[N],dp[N][N*4],pre[N][N*4];
vector<int> lvt;

ll power(ll x,int y) {
    if (y == 0) return 1;

    ll tam = power(x*x %oo, y>>1);
    if (y&1) tam = tam * x %oo;

    return tam;
}

int main()
{
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i=1;i<=n;++i) {
        cin >> a[i].fi >> a[i].se;
        lvt.pb(a[i].fi); lvt.pb(a[i].se);
    }

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

    for (int e=0;e<(int)lvt.size();++e) {
        b[++m] = {lvt[e],lvt[e]};
        if (e < (int)lvt.size() - 1 && lvt[e]+1 < lvt[e+1]) b[++m] = {lvt[e]+1,lvt[e+1]-1};
    }

    dp[0][0] = 1;
    for (int i=0;i<=n;++i) pre[i][0] = 1;
    for (int j=0;j<=m;++j) pre[0][j] = 1;

    for (int i=1;i<=n+2;++i) inv[i] = power(i,oo-2);

    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            dp[i][j] = dp[i][j-1];
            if (a[i].fi > b[j].se || a[i].se < b[j].fi) {
                pre[i][j] = (pre[i-1][j] + dp[i][j]) %oo;
                continue;
            }

            int len = b[j].se - b[j].fi + 1; int num = -1;
            ll C = len - 1;

            dp[i][j] = (dp[i][j] + pre[i-1][j-1] * len) %oo;

            if (len >= 2) {
                for (int k=2;k<=i;++k) {
                    if (a[i-k+1].fi > b[j].se || a[i-k+1].se < b[j].fi) continue;

                    ++num;
                    C = C * (num + len) %oo * inv[num+2] %oo;

                    dp[i][j] = (dp[i][j] + pre[i-k][j-1] * C) %oo;
                }
            }

            pre[i][j] = (pre[i-1][j] + dp[i][j]) %oo;
        }

    for (int i=1;i<=n;++i) res = (res + dp[i][m]) %oo;
    cout << res;

    return 0;
}

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