Submission #245129

#	Time	Username	Problem	Language	Result	Execution time	Memory
245129		HuyQuang_re_Zero	Boat (APIO16_boat)	C++14	9 / 100	35 ms	22008 KiB

boat

#include <bits/stdc++.h>
#define ll long long
#define N 1000001
using namespace std;
const ll mod=round(1e9)+7;
ll gt[N],ng[N],sum,f[2001][2001];
long long C(int k,int n)
{
    if(k>n) return 0;
    return gt[n]*ng[k]%mod*ng[n-k]%mod;
}
int i,j,k,n,m;
struct pt { int l,r; };
pt b[N],a[N];
set <int> s;
ll lt(ll a,ll b)
{
    if(b==0) return 1;
    ll tg=lt(a,b/2);
    if(b%2==0) return tg*tg%mod;
    return tg*tg%mod*a%mod;
}
int main()
{
   // freopen("ntu.inp","r",stdin);
    //freopen("ntu.out","w",stdout);
    sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
        s.insert(a[i].l); s.insert(a[i].r);
        sum+=a[i].r-a[i].l+1;
    }
    gt[0]=1;
    for(i=1;i<=sum;i++) gt[i]=gt[i-1]*i%mod;
    ng[sum]=lt(gt[sum],mod-2);
    for(i=sum-1;i>=0;i--) ng[i]=ng[i+1]*(i+1)%mod;
    for(set <int>::iterator it=s.begin();it!=s.end();it++)
    {
        b[++m]={ (*it),(*it) };
        set <int>::iterator it2=it; it2++;
        if(it2!=s.end() && (*it)+1<(*it2)) b[++m]={ (*it)+1,(*it2)-1 };
    }
    for(i=0;i<=n;i++) f[i][0]=1;
    for(i=0;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f[i][j]=(f[i][j-1]+f[i-1][j]-f[i-1][j-1])%mod;
            for(k=i;i-k<=b[j].r-b[j].l && k>=1;k--)
            {
                if(a[k].r<b[j].l || a[k].l>b[j].r) break;
                f[i][j]=(f[i][j]+f[k-1][j-1]*C(i-k+1,b[j].r-b[j].l+1))%mod;
            }
          //  cerr<<i<<" "<<j<<" "<<f[i][j]<<'\n';
        }
    cout<<(f[n][m]-1+mod)%mod;
}

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