#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<numeric> //gcd(a,b)
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
//#include "aliens.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int int64_t
const int mxn=1000+10,minf=-1e18,mod=1e9+7,inf=1e18,lg=30;
int dp[mxn+10][mxn+10],ncr[mxn+10][mxn+10];
//knapsack
int32_t main(){
fastio
int n;cin>>n;
vector<pii>v(n+1);
vector<int>com;
int m=inf;
for(int i=1;i<=n;i++)cin>>v[i].f>>v[i].s;
for(int i=1;i<=n;i++)com.pb(v[i].f),com.pb(v[i].s);
ncr[0][0]=1;
for(int i=1;i<=2*n;i++)for(int j=0;j<=2*n;j++){
if(j)ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%mod;
else ncr[i][j]=ncr[i-1][j];
}
for(int i=1;i<=2*n;i++)for(int j=2;j<=2*n;j++)ncr[i][j]=(ncr[i][j]+ncr[i][j-1])%mod;//choose n,all r
com.pb(minf);
sort(all(com));
com.erase(unique(all(com)),com.end());
for(auto &i:v){
i.f=lb(all(com),i.f)-com.begin();
i.s=lb(all(com),i.s)-com.begin();
}
for(int i=0;i<=2*n;i++)dp[0][i]=1;
for(int i=1;i<=n;i++){
//dp pref i,j ->ith range choose in jth segment
int sum=0;
for(int j=v[i].f;j<=v[i].s;j++){
int len,cnt=0;
if(j==v[i].f){
for(int back=i;back>=1;back--)dp[i][j]=(dp[i][j]+(dp[back-1][j-1]*1ll)%mod)%mod;
continue;
}
len=com[j]-com[j-1],cnt=0;
for(int back=i;back>=1;back--){
if(v[back].f<=j&&j<=v[back].s)cnt++;//->can choose
//cout<<len<<" "<<cnt<<" "<<back<<" "<<dp[back-1][j-1]<<" "<<ncr[len][cnt]<<"B\n";
dp[i][j]=(dp[i][j]+(dp[back-1][j-1]*(ncr[len][cnt]))%mod)%mod;
}
}
for(int j=1;j<com.size();j++)dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
// for(int j=0;j<com.size();j++)cout<<dp[i][j]<<" ";
// cout<<'\n';
}
int ans=0;
for(int i=1;i<=n;i++)ans=(ans+dp[i][com.size()-1])%mod;
cout<<ans;
}
/*
3
1 3
2 5
1 6
->63
2
1 4
2 5
//1 2 3 4 5
1 1 1 1
//1 2 3 4 5
1 3 4 5 5
->18
dp i = i-1,i
*/
Compilation message
boat.cpp: In function 'int32_t main()':
boat.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=1;j<com.size();j++)dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
| ~^~~~~~~~~~~
boat.cpp:60:7: warning: unused variable 'sum' [-Wunused-variable]
60 | int sum=0;
| ^~~
boat.cpp:41:6: warning: unused variable 'm' [-Wunused-variable]
41 | int m=inf;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12376 KB |
Output is correct |
2 |
Correct |
12 ms |
12376 KB |
Output is correct |
3 |
Correct |
11 ms |
12380 KB |
Output is correct |
4 |
Correct |
11 ms |
12504 KB |
Output is correct |
5 |
Correct |
11 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
12380 KB |
Output is correct |
7 |
Correct |
12 ms |
12636 KB |
Output is correct |
8 |
Correct |
11 ms |
12376 KB |
Output is correct |
9 |
Correct |
11 ms |
12460 KB |
Output is correct |
10 |
Correct |
11 ms |
12368 KB |
Output is correct |
11 |
Correct |
11 ms |
12376 KB |
Output is correct |
12 |
Correct |
11 ms |
12412 KB |
Output is correct |
13 |
Correct |
11 ms |
12380 KB |
Output is correct |
14 |
Correct |
11 ms |
12380 KB |
Output is correct |
15 |
Correct |
12 ms |
12464 KB |
Output is correct |
16 |
Correct |
10 ms |
11100 KB |
Output is correct |
17 |
Correct |
10 ms |
11100 KB |
Output is correct |
18 |
Correct |
10 ms |
11356 KB |
Output is correct |
19 |
Correct |
10 ms |
11100 KB |
Output is correct |
20 |
Correct |
10 ms |
11132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12376 KB |
Output is correct |
2 |
Correct |
12 ms |
12376 KB |
Output is correct |
3 |
Correct |
11 ms |
12380 KB |
Output is correct |
4 |
Correct |
11 ms |
12504 KB |
Output is correct |
5 |
Correct |
11 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
12380 KB |
Output is correct |
7 |
Correct |
12 ms |
12636 KB |
Output is correct |
8 |
Correct |
11 ms |
12376 KB |
Output is correct |
9 |
Correct |
11 ms |
12460 KB |
Output is correct |
10 |
Correct |
11 ms |
12368 KB |
Output is correct |
11 |
Correct |
11 ms |
12376 KB |
Output is correct |
12 |
Correct |
11 ms |
12412 KB |
Output is correct |
13 |
Correct |
11 ms |
12380 KB |
Output is correct |
14 |
Correct |
11 ms |
12380 KB |
Output is correct |
15 |
Correct |
12 ms |
12464 KB |
Output is correct |
16 |
Correct |
10 ms |
11100 KB |
Output is correct |
17 |
Correct |
10 ms |
11100 KB |
Output is correct |
18 |
Correct |
10 ms |
11356 KB |
Output is correct |
19 |
Correct |
10 ms |
11100 KB |
Output is correct |
20 |
Correct |
10 ms |
11132 KB |
Output is correct |
21 |
Incorrect |
172 ms |
12544 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
9168 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12376 KB |
Output is correct |
2 |
Correct |
12 ms |
12376 KB |
Output is correct |
3 |
Correct |
11 ms |
12380 KB |
Output is correct |
4 |
Correct |
11 ms |
12504 KB |
Output is correct |
5 |
Correct |
11 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
12380 KB |
Output is correct |
7 |
Correct |
12 ms |
12636 KB |
Output is correct |
8 |
Correct |
11 ms |
12376 KB |
Output is correct |
9 |
Correct |
11 ms |
12460 KB |
Output is correct |
10 |
Correct |
11 ms |
12368 KB |
Output is correct |
11 |
Correct |
11 ms |
12376 KB |
Output is correct |
12 |
Correct |
11 ms |
12412 KB |
Output is correct |
13 |
Correct |
11 ms |
12380 KB |
Output is correct |
14 |
Correct |
11 ms |
12380 KB |
Output is correct |
15 |
Correct |
12 ms |
12464 KB |
Output is correct |
16 |
Correct |
10 ms |
11100 KB |
Output is correct |
17 |
Correct |
10 ms |
11100 KB |
Output is correct |
18 |
Correct |
10 ms |
11356 KB |
Output is correct |
19 |
Correct |
10 ms |
11100 KB |
Output is correct |
20 |
Correct |
10 ms |
11132 KB |
Output is correct |
21 |
Incorrect |
172 ms |
12544 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |