Submission #47154

#	Time	Username	Problem	Language	Result	Execution time	Memory
47154		PowerOfNinjaGo	Boat (APIO16_boat)	C++17	100 / 100	1271 ms	9164 KiB

boat

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 505;
const int md = 1e9+7;
void add(int &a, int b)
{
    a += b;
    if(a>= md) a-= md;
}
int mul(int a, int b)
{
    return (1LL*a*b)%md;
}
int expo(int a, int b)
{
    if(b == 0) return 1;
    int x = expo(a, b/2);
    int y = mul(x, x);
    if(b%2) y = mul(y, a);
    return y;
}
int inv(int x)
{
    return expo(x, md-2);
}
int a[maxn];
int b[maxn];
int qu[maxn][2*maxn];
int f[maxn][2*maxn];
int sum[maxn][2*maxn];
int mem[maxn][2*maxn];
int invfac[maxn];
int n;
vi vec;
int g(int L, int R, int intv)
{
    //cout << L << ' ' << R << ' ' << intv << endl;
    int k = qu[R][intv]-qu[L-1][intv]-1;
    int sz = vec[intv+1]-vec[intv];
    if(mem[k][intv] != -1) return mem[k][intv];
    int res = 1;
    for(int i = sz; i<= sz+k; i++) res = mul(res, i);
    res = mul(res, invfac[k+1]);
    return mem[k][intv] = res;
}
int main()
{
    memset(mem, -1, sizeof mem);
    cin >> n;
    invfac[0] = 1;
    for(int i = 1; i<= n; i++) invfac[i] = mul(invfac[i-1], inv(i));
    for(int i = 1; i<= n; i++)
    {
        cin >> a[i] >> b[i];
        b[i]++;
        vec.pb(a[i]); vec.pb(b[i]);
    }
    sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end())-vec.begin());
    for(int i = 1; i<= n; i++)
    {
        a[i] = lower_bound(vec.begin(), vec.end(), a[i])-vec.begin();
        b[i] = lower_bound(vec.begin(), vec.end(), b[i])-vec.begin();
    }
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            qu[i][j] = qu[i-1][j] + (a[i]<= j && j< b[i]);
        }
    }
    for(int j = 0; j< (int) vec.size()-1; j++) sum[0][j] = 1;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            if(a[i]<= j && j <b[i])
            {
                for(int a = 0; a< i ; a++)
                {
                    int sm;
                    if(j == 0 && a == 0) sm = 1;
                    else if(j == 0) sm = 0;
                    else sm = sum[a][j-1];
                    //cout << sm << endl;
                    add(f[i][j], mul(sm, g(a+1, i, j)));
                }
            }
            //printf("f[%d][%d] = %d\n", i, j, f[i][j]);
            sum[i][j] = j?sum[i][j-1]:0;
            add(sum[i][j], f[i][j]);
        }
    }
    int res = 0;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            add(res, f[i][j]);
        }
    }
    cout << res << endl;
}

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