Submission #545629

#	Time	Username	Problem	Language	Result	Execution time	Memory
545629		flashhh	Boat (APIO16_boat)	C++14	0 / 100	124 ms	12112 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];
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()
{
    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 j=0;j<=m;++j) pre[0][j] = 1;

    for (int i=1;i<=n;++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];

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

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

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

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

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

    return 0;
}

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