#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define X first
#define Y second
#define pb push_back
using namespace std;
const int N = 1010;
const ll MOD = 1e9 + 7;
ll n, intcnt, l[N], r[N];
ll siz[N], fact[N], povrh[N][N], inv[N];
ll dp[N][N], calc[N][N];
int u[N][N];
vector<pii> intv;
vector<ll> v;
ll add(ll a, ll b){
return (a + b >= MOD ? a + b - MOD : a + b);
}
ll mult(ll a, ll b){
return a * b % MOD;
}
ll fastpow(ll b, ll e){
ll ret = 1;
while(e){
if(e & 1) ret = mult(ret, b);
b = mult(b, b);
e >>= 1;
}
return ret;
}
ll divd(ll a, ll b){
return mult(a, fastpow(b, MOD - 2));
}
void precompute(){
fact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = mult(fact[i - 1], i);
inv[i] = fastpow(fact[i], MOD - 2);
}
for(int i = 0; i < N; i++){
for(int j = 0; j <= i; j++){
if(j == 0 || j == i) povrh[i][j] = 1;
else povrh[i][j] = add(povrh[i - 1][j - 1], povrh[i - 1][j]);
}
}
for(int i = 0; i < intcnt; i++){
for(ll k = 1; k <= n; k++){
ll sfact = 1;
for(ll j = 1; j <= k; j++){
sfact = mult(sfact, siz[i] - j + 1);
calc[i][k] = add(calc[i][k], mult(povrh[k - 1][j - 1], mult(sfact, inv[j])));
}
}
}
}
ll DP(int x, int b){
if(b >= intcnt) return 1;
if(dp[x][b] != -1) return dp[x][b];
dp[x][b] = DP(x, b + 1);
int cnt = 0;
for(int i = x; i < n; i++){
cnt += u[i][b];
if(u[i][b]) dp[x][b] = add(dp[x][b], mult(calc[b][cnt], DP(i + 1, b + 1)));
}
return dp[x][b];
}
int main(){
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = -1;
scanf("%lld", &n);
for(int i = 0; i < n; i++){
scanf("%lld%lld", &l[i], &r[i]);
v.pb(l[i]);
v.pb(r[i] + 1);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(int i = 0; i < v.size() - 1; i++){
intv.pb({v[i], v[i + 1] - 1});
}
intcnt = intv.size();
for(int i = 0; i < intcnt; i++) siz[i] = intv[i].Y - intv[i].X + 1;
for(int i = 0; i < n; i++){
for(ll j = 0; j < intcnt; j++){
if(intv[j].X >= l[i] && intv[j].Y <= r[i]){
u[i][j] = true;
}
}
}
precompute();
printf("%lld\n", add(DP(0, 0), MOD - 1));
return 0;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < v.size() - 1; i++){
| ~~^~~~~~~~~~~~~~
boat.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
boat.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%lld%lld", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
866 ms |
25212 KB |
Output is correct |
2 |
Correct |
885 ms |
25168 KB |
Output is correct |
3 |
Correct |
875 ms |
25036 KB |
Output is correct |
4 |
Correct |
881 ms |
24916 KB |
Output is correct |
5 |
Correct |
868 ms |
25004 KB |
Output is correct |
6 |
Correct |
885 ms |
25236 KB |
Output is correct |
7 |
Correct |
892 ms |
25316 KB |
Output is correct |
8 |
Correct |
887 ms |
25412 KB |
Output is correct |
9 |
Correct |
886 ms |
25236 KB |
Output is correct |
10 |
Correct |
893 ms |
25292 KB |
Output is correct |
11 |
Correct |
907 ms |
25380 KB |
Output is correct |
12 |
Correct |
894 ms |
25248 KB |
Output is correct |
13 |
Correct |
886 ms |
25284 KB |
Output is correct |
14 |
Correct |
887 ms |
25532 KB |
Output is correct |
15 |
Correct |
883 ms |
25264 KB |
Output is correct |
16 |
Correct |
164 ms |
18736 KB |
Output is correct |
17 |
Correct |
178 ms |
18696 KB |
Output is correct |
18 |
Correct |
169 ms |
18636 KB |
Output is correct |
19 |
Correct |
188 ms |
18708 KB |
Output is correct |
20 |
Correct |
174 ms |
18636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
866 ms |
25212 KB |
Output is correct |
2 |
Correct |
885 ms |
25168 KB |
Output is correct |
3 |
Correct |
875 ms |
25036 KB |
Output is correct |
4 |
Correct |
881 ms |
24916 KB |
Output is correct |
5 |
Correct |
868 ms |
25004 KB |
Output is correct |
6 |
Correct |
885 ms |
25236 KB |
Output is correct |
7 |
Correct |
892 ms |
25316 KB |
Output is correct |
8 |
Correct |
887 ms |
25412 KB |
Output is correct |
9 |
Correct |
886 ms |
25236 KB |
Output is correct |
10 |
Correct |
893 ms |
25292 KB |
Output is correct |
11 |
Correct |
907 ms |
25380 KB |
Output is correct |
12 |
Correct |
894 ms |
25248 KB |
Output is correct |
13 |
Correct |
886 ms |
25284 KB |
Output is correct |
14 |
Correct |
887 ms |
25532 KB |
Output is correct |
15 |
Correct |
883 ms |
25264 KB |
Output is correct |
16 |
Correct |
164 ms |
18736 KB |
Output is correct |
17 |
Correct |
178 ms |
18696 KB |
Output is correct |
18 |
Correct |
169 ms |
18636 KB |
Output is correct |
19 |
Correct |
188 ms |
18708 KB |
Output is correct |
20 |
Correct |
174 ms |
18636 KB |
Output is correct |
21 |
Correct |
1064 ms |
24536 KB |
Output is correct |
22 |
Correct |
1055 ms |
24832 KB |
Output is correct |
23 |
Correct |
1028 ms |
24496 KB |
Output is correct |
24 |
Correct |
1035 ms |
24564 KB |
Output is correct |
25 |
Correct |
1088 ms |
24472 KB |
Output is correct |
26 |
Correct |
1136 ms |
24292 KB |
Output is correct |
27 |
Correct |
1168 ms |
24500 KB |
Output is correct |
28 |
Correct |
1144 ms |
24360 KB |
Output is correct |
29 |
Correct |
1148 ms |
24452 KB |
Output is correct |
30 |
Correct |
889 ms |
25412 KB |
Output is correct |
31 |
Correct |
893 ms |
25292 KB |
Output is correct |
32 |
Correct |
882 ms |
25284 KB |
Output is correct |
33 |
Correct |
893 ms |
25292 KB |
Output is correct |
34 |
Correct |
897 ms |
25444 KB |
Output is correct |
35 |
Correct |
870 ms |
25036 KB |
Output is correct |
36 |
Correct |
878 ms |
25092 KB |
Output is correct |
37 |
Correct |
875 ms |
25132 KB |
Output is correct |
38 |
Correct |
871 ms |
25064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
16596 KB |
Output is correct |
2 |
Correct |
16 ms |
16604 KB |
Output is correct |
3 |
Correct |
17 ms |
16592 KB |
Output is correct |
4 |
Correct |
17 ms |
16688 KB |
Output is correct |
5 |
Correct |
19 ms |
16624 KB |
Output is correct |
6 |
Correct |
19 ms |
16704 KB |
Output is correct |
7 |
Correct |
20 ms |
16680 KB |
Output is correct |
8 |
Correct |
18 ms |
16664 KB |
Output is correct |
9 |
Correct |
19 ms |
16596 KB |
Output is correct |
10 |
Correct |
20 ms |
16596 KB |
Output is correct |
11 |
Correct |
19 ms |
16668 KB |
Output is correct |
12 |
Correct |
17 ms |
16668 KB |
Output is correct |
13 |
Correct |
18 ms |
16596 KB |
Output is correct |
14 |
Correct |
17 ms |
16708 KB |
Output is correct |
15 |
Correct |
18 ms |
16700 KB |
Output is correct |
16 |
Correct |
13 ms |
16212 KB |
Output is correct |
17 |
Correct |
13 ms |
16212 KB |
Output is correct |
18 |
Correct |
13 ms |
16212 KB |
Output is correct |
19 |
Correct |
13 ms |
16236 KB |
Output is correct |
20 |
Correct |
12 ms |
16168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
866 ms |
25212 KB |
Output is correct |
2 |
Correct |
885 ms |
25168 KB |
Output is correct |
3 |
Correct |
875 ms |
25036 KB |
Output is correct |
4 |
Correct |
881 ms |
24916 KB |
Output is correct |
5 |
Correct |
868 ms |
25004 KB |
Output is correct |
6 |
Correct |
885 ms |
25236 KB |
Output is correct |
7 |
Correct |
892 ms |
25316 KB |
Output is correct |
8 |
Correct |
887 ms |
25412 KB |
Output is correct |
9 |
Correct |
886 ms |
25236 KB |
Output is correct |
10 |
Correct |
893 ms |
25292 KB |
Output is correct |
11 |
Correct |
907 ms |
25380 KB |
Output is correct |
12 |
Correct |
894 ms |
25248 KB |
Output is correct |
13 |
Correct |
886 ms |
25284 KB |
Output is correct |
14 |
Correct |
887 ms |
25532 KB |
Output is correct |
15 |
Correct |
883 ms |
25264 KB |
Output is correct |
16 |
Correct |
164 ms |
18736 KB |
Output is correct |
17 |
Correct |
178 ms |
18696 KB |
Output is correct |
18 |
Correct |
169 ms |
18636 KB |
Output is correct |
19 |
Correct |
188 ms |
18708 KB |
Output is correct |
20 |
Correct |
174 ms |
18636 KB |
Output is correct |
21 |
Correct |
1064 ms |
24536 KB |
Output is correct |
22 |
Correct |
1055 ms |
24832 KB |
Output is correct |
23 |
Correct |
1028 ms |
24496 KB |
Output is correct |
24 |
Correct |
1035 ms |
24564 KB |
Output is correct |
25 |
Correct |
1088 ms |
24472 KB |
Output is correct |
26 |
Correct |
1136 ms |
24292 KB |
Output is correct |
27 |
Correct |
1168 ms |
24500 KB |
Output is correct |
28 |
Correct |
1144 ms |
24360 KB |
Output is correct |
29 |
Correct |
1148 ms |
24452 KB |
Output is correct |
30 |
Correct |
889 ms |
25412 KB |
Output is correct |
31 |
Correct |
893 ms |
25292 KB |
Output is correct |
32 |
Correct |
882 ms |
25284 KB |
Output is correct |
33 |
Correct |
893 ms |
25292 KB |
Output is correct |
34 |
Correct |
897 ms |
25444 KB |
Output is correct |
35 |
Correct |
870 ms |
25036 KB |
Output is correct |
36 |
Correct |
878 ms |
25092 KB |
Output is correct |
37 |
Correct |
875 ms |
25132 KB |
Output is correct |
38 |
Correct |
871 ms |
25064 KB |
Output is correct |
39 |
Correct |
18 ms |
16596 KB |
Output is correct |
40 |
Correct |
16 ms |
16604 KB |
Output is correct |
41 |
Correct |
17 ms |
16592 KB |
Output is correct |
42 |
Correct |
17 ms |
16688 KB |
Output is correct |
43 |
Correct |
19 ms |
16624 KB |
Output is correct |
44 |
Correct |
19 ms |
16704 KB |
Output is correct |
45 |
Correct |
20 ms |
16680 KB |
Output is correct |
46 |
Correct |
18 ms |
16664 KB |
Output is correct |
47 |
Correct |
19 ms |
16596 KB |
Output is correct |
48 |
Correct |
20 ms |
16596 KB |
Output is correct |
49 |
Correct |
19 ms |
16668 KB |
Output is correct |
50 |
Correct |
17 ms |
16668 KB |
Output is correct |
51 |
Correct |
18 ms |
16596 KB |
Output is correct |
52 |
Correct |
17 ms |
16708 KB |
Output is correct |
53 |
Correct |
18 ms |
16700 KB |
Output is correct |
54 |
Correct |
13 ms |
16212 KB |
Output is correct |
55 |
Correct |
13 ms |
16212 KB |
Output is correct |
56 |
Correct |
13 ms |
16212 KB |
Output is correct |
57 |
Correct |
13 ms |
16236 KB |
Output is correct |
58 |
Correct |
12 ms |
16168 KB |
Output is correct |
59 |
Correct |
1157 ms |
25292 KB |
Output is correct |
60 |
Correct |
1134 ms |
25352 KB |
Output is correct |
61 |
Correct |
1116 ms |
25280 KB |
Output is correct |
62 |
Correct |
1165 ms |
25164 KB |
Output is correct |
63 |
Correct |
1153 ms |
25412 KB |
Output is correct |
64 |
Correct |
1301 ms |
25424 KB |
Output is correct |
65 |
Correct |
1296 ms |
25320 KB |
Output is correct |
66 |
Correct |
1302 ms |
25524 KB |
Output is correct |
67 |
Correct |
1302 ms |
25448 KB |
Output is correct |
68 |
Correct |
1303 ms |
25376 KB |
Output is correct |
69 |
Correct |
1193 ms |
25408 KB |
Output is correct |
70 |
Correct |
1191 ms |
25340 KB |
Output is correct |
71 |
Correct |
1201 ms |
25340 KB |
Output is correct |
72 |
Correct |
1180 ms |
25396 KB |
Output is correct |
73 |
Correct |
1198 ms |
25496 KB |
Output is correct |
74 |
Correct |
220 ms |
18756 KB |
Output is correct |
75 |
Correct |
222 ms |
18760 KB |
Output is correct |
76 |
Correct |
227 ms |
18664 KB |
Output is correct |
77 |
Correct |
225 ms |
18816 KB |
Output is correct |
78 |
Correct |
226 ms |
18696 KB |
Output is correct |