| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 733037 |
2023-04-30T03:21:43 Z |
minhcool |
Boat (APIO16_boat) |
C++17 |
|
45 ms |
32532 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1005;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, a[N], b[N];
int dp[N][N];
vector<int> vc;
int le[N], ri[N];
int prep[N][N];
int inv[N];
int binpw(int base, int pw){
int ans = 1;
while(pw){
ans = (ans * base) % mod;
base = (base * base) % mod;
pw >>= 1;
}
return ans;
}
int pre(int x, int ind){
if(!inv[0]){
inv[0] = 1;
for(int i = 1; i <= n; i++){
inv[i] = binpw(i, mod - 2) % mod;
}
}
int ans = 1;
prep[ind][0] = 1;
for(int i = 1; i <= min(x, n); i++){
ans = (ans * (x - i + 1)) % mod;
ans = (ans * inv[i]) % mod;
prep[ind][i] = ans;
}
}
int pref[N][N];
void process(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
a[i]--;
vc.pb(a[i]), vc.pb(b[i]);
}
sort(vc.begin(), vc.end());
for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
for(int i = 1; i <= n; i++){
le[i] = lower_bound(vc.begin(), vc.end(), a[i]) - vc.begin();
le[i]++;
ri[i] = lower_bound(vc.begin(), vc.end(), b[i]) - vc.begin();
}
dp[0][0] = pref[0][0] = 1;
for(int j = 1; j < vc.size(); j++) dp[0][j] = pref[0][j] = 1;
for(int i = 1; i <= n; i++){
dp[i][0] = pref[i][0] = 1;
for(int j = 1; j < vc.size(); j++){
if(le[i] > j || ri[i] < j){
//pref[i][j] = pref[i - 1][j];
continue;
}
dp[i][j] = (pref[i - 1][j - 1] * prep[j][1]) % mod;
//dp[i][j] = dp[i - 1][j];
int sum = 0, cnt = 1;
for(int k = i - 1; k >= 1; k--){
//if(le[k] > j || ri[k] < j) break;
if(le[k] <= j && ri[k] >= j){
cnt++;
sum = (sum + pref[j][cnt]) % mod;
dp[i][j] = (dp[i][j] + (pref[k - 1][j - 1] * sum)) % mod;
//dp[i][j] += dp[i - 1][j - 1] * prep;
}
}
//pref[i][j] += pref[i - 1][j];
}
for(int j = 1; j < vc.size(); j++){
pref[i][j] = (pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + dp[i][j] + 3 * mod) % mod;
}
}
for(int i = 0; i <= n; i++){
//for(int j = 0; j < vc.size(); j++) cout << i << " " << j << " " << pref[i][j] << "\n";
}
cout << (pref[n][vc.size() - 1] + mod - 1) % mod << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
Compilation message
boat.cpp: In function 'long long int pre(long long int, long long int)':
boat.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
52 | }
| ^
boat.cpp: In function 'void process()':
boat.cpp:64:19: 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]
64 | for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
| ~~^~~~~~~~~~~
boat.cpp:71:19: 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]
71 | for(int j = 1; j < vc.size(); j++) dp[0][j] = pref[0][j] = 1;
| ~~^~~~~~~~~~~
boat.cpp:74:20: 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]
74 | for(int j = 1; j < vc.size(); j++){
| ~~^~~~~~~~~~~
boat.cpp:93:20: 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]
93 | for(int j = 1; j < vc.size(); j++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
32532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
32532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
32460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
32532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
