| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 23224 |
2017-05-05T07:24:36 Z |
14kg |
Boat (APIO16_boat) |
C++11 |
|
1463 ms |
5000 KB |
#include <stdio.h>
#include <map>
#include <set>
#include <algorithm>
#define MOD 1000000007
#define min2(x,y) (x<y?x:y)
using namespace std;
int n, w_len, d[501][1503];
bool check[501][1503];
pair<int, int> r[501], w[1503];
set<int> S;
map<int,int> M;
int f(int lev, int y) {
if (lev == 0) return 1;
if (!check[lev][y]) {
check[lev][y] = true, d[lev][y] = f(lev - 1, y);
for (int i = r[lev].first; i <= min2(r[lev].second, y); i++) {
long long temp = f(lev - 1, i - 1), temp2 = w[i].second - w[i].first + 1;
temp = (temp*temp2) % MOD;
d[lev][y] = (d[lev][y] + temp) % MOD;
}
} return d[lev][y];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &r[i].first, &r[i].second);
S.insert(r[i].first), S.insert(r[i].second);
}
auto it1 = S.begin(), it2 = it1;
it2++, w[++w_len] = { 0,*it1 - 1 };
while (it2 != S.end()) {
M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };
if (*it1 + 1 <= *it2 - 1) w[++w_len] = { *it1 + 1,*it2 - 1 };
it1++, it2++;
} M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };
for (int i = 1; i <= n; i++) {
r[i].first = M[r[i].first];
r[i].second = M[r[i].second];
}
int res = f(n, w_len);
printf("%d", res ? res - 1 : MOD- 1);
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
boat.cpp:29:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &r[i].first, &r[i].second);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 13 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 13 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 21 |
Incorrect |
1463 ms |
5000 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
4868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 13 |
Correct |
6 ms |
4868 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4868 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4868 KB |
Output is correct |
| 21 |
Incorrect |
1463 ms |
5000 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
