Submission #1076388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076388		alexdd	Boat (APIO16_boat)	C++17	100 / 100	1196 ms	8664 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;
        }
        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;
}

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