Submission #1076365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076365		alexdd	Boat (APIO16_boat)	C++17	9 / 100	2074 ms	4108 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put(a*a%MOD,exp/2);
    else
        return put(a*a%MOD,exp/2)*a%MOD;
}
int n,cate;
int le[505],ri[505];
map<int,int> mp,nrm;
int invnrm[1005],nr[1005];
int dp[1005][505];
int fact[1005],invf[1005];
int comb(int x, int y)
{
    if(x<y)
        return 0;
    return fact[x]*invf[y]%MOD*invf[x-y]%MOD;
}
signed main()
{
    fact[0]=1;
    for(int i=1;i<=1000;i++)
        fact[i]=fact[i-1]*i%MOD;
    invf[1000]=put(fact[1000],MOD-2);
    for(int i=999;i>=0;i--)
        invf[i]=invf[i+1]*(i+1)%MOD;

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>le[i]>>ri[i];
        mp[le[i]]++;
        mp[ri[i]]++;
    }
    for(auto it:mp)
    {
        if(it.second)
        {
            nrm[it.first]=++cate;
            invnrm[cate]=it.first;
        }
    }
    for(int i=1;i<=cate;i++)
    {
        nr[i] = invnrm[i]-invnrm[i-1];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        le[i] = nrm[le[i]];
        ri[i] = nrm[ri[i]];
        int copnr = nr[le[i]];
        nr[le[i]]=1;
        for(int ult=ri[i];ult>=le[i];ult--)
        {
            for(int cnt=min(i,nr[ult]);cnt>1;cnt--)
            {
                //dp[ult][cnt]= (dp[ult][cnt] + dp[ult][cnt-1] * (nr[ult]-cnt+1)%MOD * put(cnt,MOD-2))%MOD;
                dp[ult][cnt]= (dp[ult][cnt] + dp[ult][cnt-1] * put(comb(nr[ult],cnt-1),MOD-2)%MOD * comb(nr[ult],cnt))%MOD;
            }
            for(int j=0;j<ult;j++)
                for(int orice=0;orice<i;orice++)
                    dp[ult][1] = (dp[ult][1] + dp[j][orice]*nr[ult])%MOD;
        }
        nr[le[i]]=copnr;
    }
    int rez=0;
    for(int ult=1;ult<=cate;ult++)
        for(int cnt=1;cnt<=n;cnt++)
            rez = (rez + dp[ult][cnt])%MOD;
    cout<<rez;
    return 0;
}
/**

impartim intervalul [1,1e9] in intervale relevante, o sa avem maxim 1000 intervale relevante

dp[i][ult][cnt] = in cate moduri pot primele i scoli barci, a.i. ultimele cnt numere sa fie aflate in intervalul ult

daca i poate sa aleaga intervalul ult

dp[i][ult][1] = dp[i-1][ult][1] + sum(dp[i-1][orice<ult][orice])*nr[ult]
pt cnt>=2  dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] / comb(nr[ult],cnt-1) * comb(nr[ult],cnt)
pt cnt>=2  dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] * (nr[ult]-cnt+1) / cnt

(nr[ult]-cnt+1) / cnt

*/

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