# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
547892 |
2022-04-12T01:18:12 Z |
Olympia |
Boat (APIO16_boat) |
C++17 |
|
273 ms |
4348 KB |
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
const int M = 1e9 + 7;
const int MOD = 1e9 + 7;
using namespace std;
int64_t binPow (int64_t x, int64_t y) {
int64_t ans = 1, res = x;
while (y) {
if (y & 1) ans *= res, ans %= MOD;
res *= res, res %= MOD, y /= 2;
}
return ans;
}
int64_t inv (int64_t x) {
return binPow(x, MOD - 2);
}
struct modint {
modint() : n(0) {}
template <class T> modint(T n) { n %= M; if (n < 0) n += M; this->n = n; }
modint & operator+=(const modint &r) { n += r.n; if (n >= M) n -= M; return *this; }
modint & operator-=(const modint &r) { n -= r.n; if (n < 0) n += M; return *this; }
modint & operator*=(const modint &r) { n = (int) ((long long) n * r.n % M); return *this; }
modint & operator--() { if (--n == -1) n = M - 1; return *this; }
modint & operator++() { if (++n == M) n = 0; return *this; }
modint operator--(int) { modint t = *this; --*this; return t; }
modint operator++(int) { modint t = *this; ++*this; return t; }
modint operator-() const { return 0 - *this; }
modint operator+() const { return *this; }
modint pow(long long k = M - 2) const {
modint f = *this, p = 1;
while (k > 0) {
if (k % 2 == 1) f *= p;
p *= p, k /= 2;
}
return f;
}
int mod() const { return M; }
friend modint operator+(modint l, const modint &r) { return l += r; }
friend modint operator-(modint l, const modint &r) { return l -= r; }
friend modint operator*(modint l, const modint &r) { return l *= r; }
friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }
friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }
friend ostream & operator<<(ostream &out, const modint &r) { return out << r.n; }
int n;
};
vector<pair<int,int>> compress (vector<pair<int,int>> &vec) {
set<int> s;
for (auto& p: vec) {
s.insert(p.first), s.insert(p.second);
}
vector<int> v; for (int i: s) v.push_back(i);
vector<pair<int,int>> grids;
grids.emplace_back(-1, -1);
for (int i = 0; i < v.size(); i++) {
grids.emplace_back(v[i], v[i]);
if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
}
return grids;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; cin >> N;
vector<pair<int,int>> points(N);
for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
vector<pair<int,int>> grid = compress(points);
modint combo[grid.size()][N + 1];
for (int i = 0; i < grid.size(); i++) {
combo[i][0] = 1;
for (int j = 1; j <= N; j++) {
combo[i][j] = (combo[i][j - 1] * ((modint)j).pow()) * (grid[i].second - grid[i].first + j);
}
}
modint dp[N + 1][grid.size()];
for (int i = 0; i <= N; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < grid.size(); i++) {
dp[0][i] = 1;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j < grid.size(); j++) {
dp[i][j] = dp[i][j - 1];
int pos = 0;
for (int k = i; k >= 1; k--) {
if (grid[j].first >= points[k - 1].first && grid[j].second <= points[k - 1].second) {
pos ++;
dp[i][j] += dp[k - 1][j - 1] * combo[j][pos];
}
}
}
}
cout << dp[N][grid.size() - 1] - 1;
}
Compilation message
boat.cpp: In function 'std::vector<std::pair<int, int> > compress(std::vector<std::pair<int, int> >&)':
boat.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
boat.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
| ~~~~~~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 0; i < grid.size(); i++) {
| ~~^~~~~~~~~~~~~
boat.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 1; i < grid.size(); i++) {
| ~~^~~~~~~~~~~~~
boat.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int j = 1; j < grid.size(); j++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
4232 KB |
Output is correct |
2 |
Correct |
266 ms |
4232 KB |
Output is correct |
3 |
Correct |
267 ms |
4256 KB |
Output is correct |
4 |
Correct |
267 ms |
4348 KB |
Output is correct |
5 |
Correct |
257 ms |
4260 KB |
Output is correct |
6 |
Correct |
191 ms |
4264 KB |
Output is correct |
7 |
Correct |
178 ms |
4260 KB |
Output is correct |
8 |
Correct |
183 ms |
4260 KB |
Output is correct |
9 |
Correct |
187 ms |
4172 KB |
Output is correct |
10 |
Correct |
180 ms |
4264 KB |
Output is correct |
11 |
Correct |
192 ms |
4232 KB |
Output is correct |
12 |
Correct |
188 ms |
4264 KB |
Output is correct |
13 |
Correct |
189 ms |
4340 KB |
Output is correct |
14 |
Correct |
173 ms |
4260 KB |
Output is correct |
15 |
Correct |
187 ms |
4260 KB |
Output is correct |
16 |
Incorrect |
56 ms |
1000 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
4232 KB |
Output is correct |
2 |
Correct |
266 ms |
4232 KB |
Output is correct |
3 |
Correct |
267 ms |
4256 KB |
Output is correct |
4 |
Correct |
267 ms |
4348 KB |
Output is correct |
5 |
Correct |
257 ms |
4260 KB |
Output is correct |
6 |
Correct |
191 ms |
4264 KB |
Output is correct |
7 |
Correct |
178 ms |
4260 KB |
Output is correct |
8 |
Correct |
183 ms |
4260 KB |
Output is correct |
9 |
Correct |
187 ms |
4172 KB |
Output is correct |
10 |
Correct |
180 ms |
4264 KB |
Output is correct |
11 |
Correct |
192 ms |
4232 KB |
Output is correct |
12 |
Correct |
188 ms |
4264 KB |
Output is correct |
13 |
Correct |
189 ms |
4340 KB |
Output is correct |
14 |
Correct |
173 ms |
4260 KB |
Output is correct |
15 |
Correct |
187 ms |
4260 KB |
Output is correct |
16 |
Incorrect |
56 ms |
1000 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
4232 KB |
Output is correct |
2 |
Correct |
266 ms |
4232 KB |
Output is correct |
3 |
Correct |
267 ms |
4256 KB |
Output is correct |
4 |
Correct |
267 ms |
4348 KB |
Output is correct |
5 |
Correct |
257 ms |
4260 KB |
Output is correct |
6 |
Correct |
191 ms |
4264 KB |
Output is correct |
7 |
Correct |
178 ms |
4260 KB |
Output is correct |
8 |
Correct |
183 ms |
4260 KB |
Output is correct |
9 |
Correct |
187 ms |
4172 KB |
Output is correct |
10 |
Correct |
180 ms |
4264 KB |
Output is correct |
11 |
Correct |
192 ms |
4232 KB |
Output is correct |
12 |
Correct |
188 ms |
4264 KB |
Output is correct |
13 |
Correct |
189 ms |
4340 KB |
Output is correct |
14 |
Correct |
173 ms |
4260 KB |
Output is correct |
15 |
Correct |
187 ms |
4260 KB |
Output is correct |
16 |
Incorrect |
56 ms |
1000 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |