Submission #40995

#	Time	Username	Problem	Language	Result	Execution time	Memory
40995		Alexa2001	Boat (APIO16_boat)	C++14	100 / 100	1440 ms	3184 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 505, Mod = 1e9 + 7;
typedef long long ll;

int start[Nmax], finish[Nmax], dp[2*Nmax][Nmax], inv[Nmax], take[Nmax], sz[2*Nmax], nr[Nmax];
int i, n, m;

int inm(int x, int y) { return (ll)x*y%Mod; }
int inm(int x, int y, int z) { return inm( inm(x, y), z ); }
void add_to(int &x, int y) { x = (x+y)%Mod; }

int power(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = inm(ans, a);
        a = inm(a, a);
        b >>= 1;
    }
    return ans;
}

void prepare()
{
    map<int,int> mp;

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> start[i] >> finish[i];
        mp[start[i]] = mp[finish[i]+1] = 1;
    }

    int cnt = 0;
    for(auto &it : mp) it.second = ++cnt;

    int lst = mp.begin()->first;
    mp.erase(mp.begin());

    for(auto &it : mp)
        sz[++m] = it.first - lst, lst = it.first;

    for(i=1; i<=n; ++i)
        start[i] = mp[start[i]], finish[i] = mp[finish[i]+1] - 1;

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

void compute(int x)
{
    int i, j;

    nr[0] = 1;
    for(i=1; i<=n; ++i)
    {
        if(i<=x) nr[i] = inm(nr[i-1], inv[i], x-i+1);
            else nr[i] = 0;
        take[i] = nr[i];

        for(j=1; j<i && j<=x; ++j)
        {
            nr[j] = inm(nr[j], inm((i-1), inv[i-j]));
            add_to(take[i], nr[j]);
        }
    }
}

int solve()
{
    int i, j, k, good;

    dp[0][0] = 1;
    for(i=1; i<=m; ++i)
    {
        compute(sz[i]);
        dp[i][0] = 1;
        for(j=1; j<=n; ++j)
        {
            dp[i][j] = dp[i-1][j];
            good = 1;

            if( !(start[j] <= i && i <= finish[j]) ) continue;

            for(k=j-1; k>=0; --k)
            {
                add_to(dp[i][j], inm(take[good], dp[i-1][k]));
                good += (start[k] <= i && i <= finish[k]);
            }
        }
    }

    int ans = 0;
    for(i=1; i<=n; ++i) add_to(ans, dp[m][i]);
    return ans;
}

int main()
{
  //  freopen("input", "r", stdin);

    prepare();
    cout << solve() << '\n';

    return 0;
}

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