# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
23492 |
2017-05-10T12:04:22 Z |
Nirjhor |
Boat (APIO16_boat) |
C++14 |
|
989 ms |
9336 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 505;
const int M = 1005;
const int MOD = 1e9 + 7;
vector <pii> v;
vector <int> z[M];
int n, m, a[N], b[N];
int x[M], y[M];
ll dp[N][M];
int sz[M], wide[M];
int comb[M][N], inverse[N];
int counter = 1;
int bigMod (int a, int e) {
if (e == -1) e = MOD - 2;
int r = 1; while (e) {
if (e & 1) r = (r * 1ll * a) % MOD;
a = (a * 1ll * a) % MOD;
e >>= 1;
}
return r;
}
// int call (int at, int range) {
// if (at > n or range > m) return 1;
// if (dp[at][range] != -1) return dp[at][range];
// ll ret = call(at, range + 1);
// int start = 0;
// while (start < sz[range] and z[range][start] < at) ++start;
// for (int i = start; i < sz[range]; ++i) {
// ret += comb[range][i - pos] * 1ll * call(z[range][i] + 1, range + 1);
// ret %= MOD;
// }
// return dp[at][range] = ret;
// }
int nCr (int n, int r) {
if (n < r) return 0;
ll res = 1ll;
for (int i = n, j = 1; j <= r; --i, ++j) {
res *= 1ll * i, res %= MOD;
res *= inverse[j], res %= MOD;
}
return res;
}
int main (int argc, char const *argv[]) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", a + i, b + i);
v.push_back({a[i], 0});
v.push_back({b[i], 1});
}
sort(v.begin(), v.end());
for (int i = 1; i < n + n; ++i) {
int one = v[i - 1].second, two = v[i].second;
int l = v[i - 1].first, r = v[i].first;
if (!one and !two) {
--r, ++counter;
if (l <= r) x[++m] = l, y[m] = r;
} else if (!one and two) {
--counter;
if (l <= r) x[++m] = l, y[m] = r;
} else if (one and two) {
++l, --counter;
if (l <= r) x[++m] = l, y[m] = r;
} else {
++l, --r;
if (counter and l <= r) x[++m] = l, y[m] = r;
++counter;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[j] <= x[i] and y[i] <= b[j]) {
z[i].push_back(j);
++sz[i];
}
}
wide[i] = y[i] - x[i] + 1;
}
for (int i = 1; i < N; ++i) {
inverse[i] = bigMod(i, -1);
}
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= sz[i]; ++j) {
comb[i][j] = nCr(wide[i] + j, j + 1);
}
}
for (int i = 0; i <= n + 1; ++i) {
dp[i][m + 1] = 1;
}
for (int i = 0; i <= m + 1; ++i) {
dp[n + 1][i] = 1;
}
for (int at = n; at; --at) {
for (int range = m; range; --range) {
dp[at][range] = dp[at][range + 1];
int start = 0;
while (start < sz[range] and z[range][start] < at) ++start;
for (int i = start; i < sz[range]; ++i) {
dp[at][range] += comb[range][i - start] * dp[z[range][i] + 1][range + 1];
dp[at][range] %= MOD;
}
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j) {
// cout << "(" << i << ", " << j << ") ---> " << dp[i][j] << endl;
// }
// }
dp[1][1] += MOD - 1, dp[1][1] %= MOD;
printf("%lld\n", dp[1][1]);
return 0;
}
Compilation message
boat.cpp: In function 'int main(int, const char**)':
boat.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
boat.cpp:57:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", a + i, b + i);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8016 KB |
Output is correct |
2 |
Correct |
6 ms |
8016 KB |
Output is correct |
3 |
Correct |
3 ms |
8016 KB |
Output is correct |
4 |
Correct |
0 ms |
8016 KB |
Output is correct |
5 |
Correct |
6 ms |
8016 KB |
Output is correct |
6 |
Correct |
0 ms |
8016 KB |
Output is correct |
7 |
Correct |
0 ms |
8016 KB |
Output is correct |
8 |
Correct |
6 ms |
8016 KB |
Output is correct |
9 |
Correct |
0 ms |
8016 KB |
Output is correct |
10 |
Correct |
3 ms |
8016 KB |
Output is correct |
11 |
Correct |
3 ms |
8016 KB |
Output is correct |
12 |
Correct |
3 ms |
8016 KB |
Output is correct |
13 |
Correct |
0 ms |
8016 KB |
Output is correct |
14 |
Correct |
0 ms |
8016 KB |
Output is correct |
15 |
Correct |
0 ms |
8016 KB |
Output is correct |
16 |
Correct |
0 ms |
8016 KB |
Output is correct |
17 |
Correct |
3 ms |
8016 KB |
Output is correct |
18 |
Correct |
0 ms |
8016 KB |
Output is correct |
19 |
Correct |
3 ms |
8016 KB |
Output is correct |
20 |
Correct |
3 ms |
8016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8016 KB |
Output is correct |
2 |
Correct |
6 ms |
8016 KB |
Output is correct |
3 |
Correct |
3 ms |
8016 KB |
Output is correct |
4 |
Correct |
0 ms |
8016 KB |
Output is correct |
5 |
Correct |
6 ms |
8016 KB |
Output is correct |
6 |
Correct |
0 ms |
8016 KB |
Output is correct |
7 |
Correct |
0 ms |
8016 KB |
Output is correct |
8 |
Correct |
6 ms |
8016 KB |
Output is correct |
9 |
Correct |
0 ms |
8016 KB |
Output is correct |
10 |
Correct |
3 ms |
8016 KB |
Output is correct |
11 |
Correct |
3 ms |
8016 KB |
Output is correct |
12 |
Correct |
3 ms |
8016 KB |
Output is correct |
13 |
Correct |
0 ms |
8016 KB |
Output is correct |
14 |
Correct |
0 ms |
8016 KB |
Output is correct |
15 |
Correct |
0 ms |
8016 KB |
Output is correct |
16 |
Correct |
0 ms |
8016 KB |
Output is correct |
17 |
Correct |
3 ms |
8016 KB |
Output is correct |
18 |
Correct |
0 ms |
8016 KB |
Output is correct |
19 |
Correct |
3 ms |
8016 KB |
Output is correct |
20 |
Correct |
3 ms |
8016 KB |
Output is correct |
21 |
Correct |
516 ms |
8808 KB |
Output is correct |
22 |
Correct |
503 ms |
8940 KB |
Output is correct |
23 |
Correct |
466 ms |
8808 KB |
Output is correct |
24 |
Correct |
483 ms |
8808 KB |
Output is correct |
25 |
Correct |
466 ms |
8808 KB |
Output is correct |
26 |
Correct |
866 ms |
9204 KB |
Output is correct |
27 |
Correct |
903 ms |
9204 KB |
Output is correct |
28 |
Correct |
893 ms |
9204 KB |
Output is correct |
29 |
Correct |
863 ms |
9204 KB |
Output is correct |
30 |
Correct |
9 ms |
8016 KB |
Output is correct |
31 |
Correct |
3 ms |
8016 KB |
Output is correct |
32 |
Correct |
9 ms |
8016 KB |
Output is correct |
33 |
Correct |
6 ms |
8016 KB |
Output is correct |
34 |
Correct |
3 ms |
8016 KB |
Output is correct |
35 |
Correct |
6 ms |
8016 KB |
Output is correct |
36 |
Correct |
6 ms |
8016 KB |
Output is correct |
37 |
Correct |
9 ms |
8016 KB |
Output is correct |
38 |
Correct |
9 ms |
8016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8016 KB |
Output is correct |
2 |
Correct |
3 ms |
8016 KB |
Output is correct |
3 |
Correct |
3 ms |
8016 KB |
Output is correct |
4 |
Correct |
0 ms |
8016 KB |
Output is correct |
5 |
Correct |
6 ms |
8016 KB |
Output is correct |
6 |
Correct |
6 ms |
8148 KB |
Output is correct |
7 |
Correct |
6 ms |
8148 KB |
Output is correct |
8 |
Correct |
6 ms |
8148 KB |
Output is correct |
9 |
Correct |
6 ms |
8148 KB |
Output is correct |
10 |
Correct |
6 ms |
8148 KB |
Output is correct |
11 |
Correct |
3 ms |
8016 KB |
Output is correct |
12 |
Correct |
3 ms |
8016 KB |
Output is correct |
13 |
Correct |
3 ms |
8016 KB |
Output is correct |
14 |
Correct |
3 ms |
8016 KB |
Output is correct |
15 |
Correct |
3 ms |
8016 KB |
Output is correct |
16 |
Correct |
3 ms |
8016 KB |
Output is correct |
17 |
Correct |
0 ms |
8016 KB |
Output is correct |
18 |
Correct |
0 ms |
8016 KB |
Output is correct |
19 |
Correct |
3 ms |
8016 KB |
Output is correct |
20 |
Correct |
3 ms |
8016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8016 KB |
Output is correct |
2 |
Correct |
6 ms |
8016 KB |
Output is correct |
3 |
Correct |
3 ms |
8016 KB |
Output is correct |
4 |
Correct |
0 ms |
8016 KB |
Output is correct |
5 |
Correct |
6 ms |
8016 KB |
Output is correct |
6 |
Correct |
0 ms |
8016 KB |
Output is correct |
7 |
Correct |
0 ms |
8016 KB |
Output is correct |
8 |
Correct |
6 ms |
8016 KB |
Output is correct |
9 |
Correct |
0 ms |
8016 KB |
Output is correct |
10 |
Correct |
3 ms |
8016 KB |
Output is correct |
11 |
Correct |
3 ms |
8016 KB |
Output is correct |
12 |
Correct |
3 ms |
8016 KB |
Output is correct |
13 |
Correct |
0 ms |
8016 KB |
Output is correct |
14 |
Correct |
0 ms |
8016 KB |
Output is correct |
15 |
Correct |
0 ms |
8016 KB |
Output is correct |
16 |
Correct |
0 ms |
8016 KB |
Output is correct |
17 |
Correct |
3 ms |
8016 KB |
Output is correct |
18 |
Correct |
0 ms |
8016 KB |
Output is correct |
19 |
Correct |
3 ms |
8016 KB |
Output is correct |
20 |
Correct |
3 ms |
8016 KB |
Output is correct |
21 |
Correct |
516 ms |
8808 KB |
Output is correct |
22 |
Correct |
503 ms |
8940 KB |
Output is correct |
23 |
Correct |
466 ms |
8808 KB |
Output is correct |
24 |
Correct |
483 ms |
8808 KB |
Output is correct |
25 |
Correct |
466 ms |
8808 KB |
Output is correct |
26 |
Correct |
866 ms |
9204 KB |
Output is correct |
27 |
Correct |
903 ms |
9204 KB |
Output is correct |
28 |
Correct |
893 ms |
9204 KB |
Output is correct |
29 |
Correct |
863 ms |
9204 KB |
Output is correct |
30 |
Correct |
9 ms |
8016 KB |
Output is correct |
31 |
Correct |
3 ms |
8016 KB |
Output is correct |
32 |
Correct |
9 ms |
8016 KB |
Output is correct |
33 |
Correct |
6 ms |
8016 KB |
Output is correct |
34 |
Correct |
3 ms |
8016 KB |
Output is correct |
35 |
Correct |
6 ms |
8016 KB |
Output is correct |
36 |
Correct |
6 ms |
8016 KB |
Output is correct |
37 |
Correct |
9 ms |
8016 KB |
Output is correct |
38 |
Correct |
9 ms |
8016 KB |
Output is correct |
39 |
Correct |
3 ms |
8016 KB |
Output is correct |
40 |
Correct |
3 ms |
8016 KB |
Output is correct |
41 |
Correct |
3 ms |
8016 KB |
Output is correct |
42 |
Correct |
0 ms |
8016 KB |
Output is correct |
43 |
Correct |
6 ms |
8016 KB |
Output is correct |
44 |
Correct |
6 ms |
8148 KB |
Output is correct |
45 |
Correct |
6 ms |
8148 KB |
Output is correct |
46 |
Correct |
6 ms |
8148 KB |
Output is correct |
47 |
Correct |
6 ms |
8148 KB |
Output is correct |
48 |
Correct |
6 ms |
8148 KB |
Output is correct |
49 |
Correct |
3 ms |
8016 KB |
Output is correct |
50 |
Correct |
3 ms |
8016 KB |
Output is correct |
51 |
Correct |
3 ms |
8016 KB |
Output is correct |
52 |
Correct |
3 ms |
8016 KB |
Output is correct |
53 |
Correct |
3 ms |
8016 KB |
Output is correct |
54 |
Correct |
3 ms |
8016 KB |
Output is correct |
55 |
Correct |
0 ms |
8016 KB |
Output is correct |
56 |
Correct |
0 ms |
8016 KB |
Output is correct |
57 |
Correct |
3 ms |
8016 KB |
Output is correct |
58 |
Correct |
3 ms |
8016 KB |
Output is correct |
59 |
Correct |
543 ms |
8940 KB |
Output is correct |
60 |
Correct |
483 ms |
8808 KB |
Output is correct |
61 |
Correct |
496 ms |
8808 KB |
Output is correct |
62 |
Correct |
566 ms |
9072 KB |
Output is correct |
63 |
Correct |
496 ms |
8808 KB |
Output is correct |
64 |
Correct |
969 ms |
9336 KB |
Output is correct |
65 |
Correct |
989 ms |
9336 KB |
Output is correct |
66 |
Correct |
976 ms |
9336 KB |
Output is correct |
67 |
Correct |
976 ms |
9336 KB |
Output is correct |
68 |
Correct |
959 ms |
9336 KB |
Output is correct |
69 |
Correct |
439 ms |
8808 KB |
Output is correct |
70 |
Correct |
439 ms |
8808 KB |
Output is correct |
71 |
Correct |
416 ms |
8808 KB |
Output is correct |
72 |
Correct |
459 ms |
8808 KB |
Output is correct |
73 |
Correct |
479 ms |
8808 KB |
Output is correct |
74 |
Correct |
109 ms |
8148 KB |
Output is correct |
75 |
Correct |
99 ms |
8148 KB |
Output is correct |
76 |
Correct |
106 ms |
8148 KB |
Output is correct |
77 |
Correct |
103 ms |
8148 KB |
Output is correct |
78 |
Correct |
113 ms |
8280 KB |
Output is correct |