Submission #1312583

#TimeUsernameProblemLanguageResultExecution timeMemory
1312583yus1f_mBoat (APIO16_boat)C++20
0 / 100
2114 ms478604 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=1000000,INF=1000000000,MOD=1000000007;
using namespace std;
void solve()
{
    ll n,num1,num2,ans=0;
    cin>>n;
    vector<pair<ll,ll>>nums;
    vector<map<ll,ll>>dp(n+1);
    for(int i=0;i<n;i++)
    {
        cin>>num1>>num2;
        nums.pb({num1,num2});
    }
    dp[1][0]=1;
    for(int i=nums[0].first;i<=nums[0].second;i++)
    {
        dp[1][i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(auto Dp:dp[i-1])
        {
            dp[i][0]=(dp[i][0]+Dp.second)%MOD;
        }
        for(auto Dp:dp[i-1])
        {
            for(int j=nums[i-1].first;j<=nums[i-1].second;j++)
            {
                if(Dp.first<j)
                {
                    dp[i][j]=(dp[i][j]+Dp.second)%MOD;
                }
            }
        }
    }
    for(auto Dp:dp[n])
    {
        ans=(ans+Dp.second)%MOD;
    }
    cout<<ans-1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...