제출 #1346963

#제출 시각아이디문제언어결과실행 시간메모리
1346963WarinchaiBoat (APIO16_boat)C++20
9 / 100
378 ms4284 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp[505][1005];
int a[505],b[505];
int md=1e9+7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<int>val;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        val.push_back(a[i]);
        val.push_back(b[i]);
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin()+1;
        b[i]=lower_bound(val.begin(),val.end(),b[i])-val.begin()+1;
    }
    //cerr<<"work\n";
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=val.size();j++)dp[i][j]=dp[i-1][j];
        for(int j=a[i];j<=b[i];j++){
            for(int k=0;k<j;k++){
                int r=val[j-1];
                int l=0;
                if(j-2>=0)l=val[j-2]+1;
                l=max(l,val[a[i]-1]);
                dp[i][j]+=(dp[i-1][k]*max(0ll,r-l+1))%md;
                dp[i][j]%=md;
            }
        }
    }
    /*for(int i=1;i<=n;i++){
        for(int j=0;j<=val.size();j++)cerr<<dp[i][j]<<" ";
        cerr<<"\n";
    }
    cerr<<"work\n";*/
    int ans=0;
    for(int i=0;i<=val.size();i++){
        ans+=dp[n][i];
        ans%=md;
    }
    cout<<(ans-1+md)%md;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...