Submission #1076386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076386		alexdd	Boat (APIO16_boat)	C++17	100 / 100	1202 ms	8504 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
const int MAXV = 2000;
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[MAXV+5],nr[MAXV+5];
int dp[MAXV+5][505];
int sumdp[MAXV+5];
int prec_inv[505];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>le[i]>>ri[i];
        mp[le[i]]++;
        mp[ri[i]]++;
        prec_inv[i] = put(i,MOD-2);
    }
    for(auto it:mp)
    {
        if(it.second)
        {
            nrm[it.first]=++cate;
            invnrm[cate]=it.first;

            cate++;
        }
    }
    for(int i=1;i<=cate;i+=2)
    {
        nr[i]=1;
        nr[i+1]=invnrm[i+2]-invnrm[i]-1;
    }
    dp[0][0]=1;
    sumdp[0]=1;
    for(int ult=1;ult<cate;ult++)
        sumdp[ult] = sumdp[ult-1];
    for(int i=1;i<=n;i++)
    {
        le[i] = nrm[le[i]];
        ri[i] = nrm[ri[i]];
        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 * prec_inv[cnt])%MOD;
            }
            dp[ult][1] = (dp[ult][1] + sumdp[ult-1]*nr[ult])%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;*/
        }
        sumdp[0]=1;
        for(int ult=1;ult<cate;ult++)
        {
            sumdp[ult] = sumdp[ult-1];
            for(int cnt=1;cnt<=i;cnt++)
                sumdp[ult] = (sumdp[ult] + dp[ult][cnt])%MOD;
        }
    }
    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: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42