Submission #978290

#	Time	Username	Problem	Language	Result	Execution time	Memory
978290		Amr	Boat (APIO16_boat)	C++17	0 / 100	26 ms	604 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=204;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)   % mod;
        y = y>>1;
        x = (x*x)  % mod;
    }
    return res;
}
ll a[N] , b[N];
map<ll,ll> com;
ll recom[N];
ll siz[N];
ll dp[N][N];
ll ch[N][N];
ll ch2[N][N];
ll p[N];
ll bit[2*N];
ll n;
void upd(ll x, ll val)
{
    x%=mod;
    while(x < N)
    {
        bit[x] = (bit[x] + val)%mod;
        x += x&(-x);
    }
}
ll get(ll x)
{
    ll res = 0;
    while(x)
    {
        res+=bit[x];
        x -= x&(-x);
    }
    return res%mod;
}
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    p[0] = 1;
    for(int i = 1; i < N; i++) p[i] = (p[i-1]*i)%mod;

    for(int i = 1; i <= n; i++) com[a[i]] = 1, com[b[i]+1] = 1;
    ll l = 1;
    for(auto it: com)
    {
        com[it.F] = l;
        recom[l++] = it.F;
    }
    for(int i = 1; i <= 2*n; i++) siz[i] = recom[i+1]-recom[i];
   // for(int i = 1; i <= 2*n; i++) cout << recom[i] << " "; cout << endl;

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            ll above = p[i];
            ll down = p[j]*p[i-j]%mod;
            ch[i][j] = (above*power(down,mod-2))%mod;
        }
    }
    for(int i = 1; i <= 2*n; i++)
    {
        if(recom[i+1]==0) continue;
        for(int j = 0; j < N; j++)
        {
            ll above = 1;

            for(int k = siz[i];  k > siz[i]-j; k--) above = (above*k)%mod;
            ll down = p[j];
            ch2[i][j] = (above*power(down,mod-2))%mod;
        }
    }
    ll all = 1;
    for(int i = 1; i <= n; i++)
    {
        ll curend = com[b[i]+1];
        ll curstart = com[a[i]];
        for(int j = curend-1; j>= curstart; j--)
        {
            dp[i][j] = ((get(j-1)+all)*siz[j])%mod;
            ll something = 0;
            //
            ll cnt = 1;

            for(int k = i-1; k >= 1; k--)
            {
                if(com[a[k]]<=j&&com[b[k]+1]>j)  {cnt++;} else continue;
                for(int kk = 2; kk <= cnt; kk++) { something = (something +ch[cnt-2+1*(k==i)][kk-2+(k==i)]*ch2[j][kk]);}
            }
            upd(j,something+dp[i][j]);
        }
    }
    cout << get(2*n+1) << endl;


}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
    while(TT--)
        solve();

    return 0;
}

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