제출 #735351

#제출 시각아이디문제언어결과실행 시간메모리
735351bin9638Boat (APIO16_boat)C++17
31 / 100
1299 ms524288 KiB
#include <bits/stdc++.h>

using namespace std;

#define N 510
#define ll long long
#define fs first
#define sc second
#define ii pair<ll,int>
#define pb push_back
#define int ll

const ll mod=1e9+7;

void selfadd(int&u,int v)
{
    u+=v;
    if(u>=mod)u-=mod;
   // u=(u+v)%mod;
}

int n,l[N],r[N];
vector<int>dp[N];

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        dp[i].resize(r[i]-l[i]+1,0);
    }
    for(int i=1;i<=n;i++)
        for(int j=l[i];j<=r[i];j++)
        {
            dp[i][j-l[i]]=1;
            if(j>l[i])
                dp[i][j-l[i]]=dp[i][j-l[i]-1]+1;
       //     cout<<i<<" "<<j<<" "<<dp[i][j-l[i]]<<endl;
            for(int k=1;k<i;k++)
            {
                if(j>r[k])
                {
                    selfadd(dp[i][j-l[i]],dp[k].back());
                    continue;
                }
                if(j<=l[k])
                    continue;
                selfadd(dp[i][j-l[i]],dp[k][j-l[k]-1]);
            }
           // cout<<i<<" "<<j<<" "<<dp[i][j-l[i]]<<endl;
        }
    int res=0;
    for(int i=1;i<=n;i++)
        selfadd(res,dp[i].back());
    cout<<(res+mod*mod)%mod;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...