| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631560 |
2022-08-18T08:38:35 Z |
CDuong |
Boat (APIO16_boat) |
C++14 |
|
2 ms |
468 KB |
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define pii pair<int, int>
using namespace std;
const int mxN = 1005;
const int mod = 1e9 + 7;
int n, ans, fact[mxN], revfact[mxN], dp[2 * mxN][mxN], pref[2 * mxN][mxN];
pii p[mxN];
vector<int> v;
vector<pii> seg;
int binpow(int x, int y){
int res = 1;
while(y != 0){
if(y % 2 == 1) res = (res * x) % mod;
x = (x * x) % mod;
y /= 2;
}
return res;
}
int calc(){
fact[0] = 1;
for(int i = 1; i < 505; ++i){
fact[i] = (fact[i - 1] * i) % mod;
}
for(int i = 0; i < 505; ++i){
revfact[i] = binpow(fact[i], mod - 2);
//cout << fact[i] << " " << revfact[i] << endl;
}
}
int rCk(int r, int k){
if(r > k) return 0;
int tmp = (fact[k] * revfact[r]) % mod;
tmp = (tmp * revfact[k - r]) % mod;
//cout << r << " " << k << " " << tmp << endl;
return tmp;
}
bool check(pii x, pii y){
if(x.ff >= y.ff && x.ss <= y.ss) return true;
return false;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("Bai3.inp", "r", stdin);
//freopen("Bai3.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> p[i].ff >> p[i].ss;
v.pb(p[i].ff);
v.pb(p[i].ss + 1);
}
calc();
sort(v.begin(), v.end());
vector<int>::iterator it = unique(v.begin(), v.end());
v.resize(distance(v.begin(), it));
seg.pb({0, 0});
for(int i = 1; i < v.size(); ++i){
seg.pb({v[i - 1], v[i] - 1});
//cout << seg[i - 1].ff << " " << seg[i - 1].ss << endl;
}
dp[0][0] = ans = 1;
//cout << rCk(1, 1) << endl;
for(int i = 1; i < seg.size(); ++i){
dp[i][0] = pref[i][0] = 1;
int dis = seg[i].ss - seg[i].ff + 1;
//cout << "seg: " << i << " " << seg[i].ff << " " << seg[i].ss << endl;
for(int j = 1; j <= n; ++j){
dp[i][j] += pref[i - 1][j];
int k = j;
while(k >= 1 && check(seg[i], p[k])){
int tmp = rCk(j - k + 1, dis);
tmp = (tmp * dp[i - 1][k - 1]);
//cout << i << " " << j << " " << k << " " << tmp << endl;
dp[i][j] += tmp;
k--;
}
pref[i][j] = dp[i][j] + pref[i - 1][j];
//cout << i << " " << j << " " << dp[i][j] << endl;
if(i == seg.size() - 1) ans += dp[i][j];
}
}
cout << ans << endl;
}
Compilation message
boat.cpp: In function 'long long int calc()':
boat.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
39 | }
| ^
boat.cpp: In function 'int main()':
boat.cpp:67:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 1; i < v.size(); ++i){
| ~~^~~~~~~~~~
boat.cpp:73:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 1; i < seg.size(); ++i){
| ~~^~~~~~~~~~~~
boat.cpp:89:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if(i == seg.size() - 1) ans += dp[i][j];
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
