| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 554406 |
2022-04-28T10:47:34 Z |
fatemetmhr |
Boat (APIO16_boat) |
C++17 |
|
340 ms |
6548 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
const int maxn5 = 5e2 + 5;
const int maxnb = 1e3 + 10;
const int mod = 1e9 + 7;
int ent[maxn5][maxn5], val[maxnb][maxn5];
int ent2[maxnb][maxn5], szb[maxnb];
int l[maxn5], r[maxn5], ansel[maxn5][maxnb];
int ansbl[maxnb];
vector <int> exx;
inline ll pw(ll a, ll b){
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b&1) ret = ret * a % mod;
return ret;
}
inline ll entof(ll n, ll r){
ll s = 1, m = 1;
for(int i = 0; i < r; i++){
s = s * (n - i) % mod;
m = m * (i + 1) % mod;
}
return (s * pw(m, mod - 2)) % mod;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> l[i] >> r[i]; // (..]
r[i]++;
exx.pb(l[i]);
exx.pb(r[i]);
}
exx.pb(0);
sort(all(exx));
exx.resize(unique(all(exx)) - exx.begin());
for(int i = 0; i < n; i++){
l[i] = lower_bound(all(exx), l[i]) - exx.begin();
r[i] = lower_bound(all(exx), r[i]) - exx.begin();
//cout << "segment " << i << ' ' << l[i] << ' ' << r[i] << endl;
}
for(int i = 1; i < exx.size(); i++){
szb[i] = exx[i] - exx[i - 1];
//cout << "a bl of " << exx[i] << ' ' << exx[i - 1] << ' ' << szb[i + 1] << endl;
}
int blsz = exx.size();
ent[0][0] = 1;
for(int i = 1; i < maxn5; i++){
ent[i][0] = 1;
for(int j = 1; j <= i; j++)
ent[i][j] = (ent[i - 1][j - 1] + ent[i - 1][j]) % mod;
}
for(int i = 1; i < blsz; i++) for(int j = 0; j < maxn5 && j <= szb[i]; j++){
ent2[i][j] = entof(szb[i], j);
}
for(int i = 1; i < blsz; i++) for(int j = 0; j < n; j++){ // bl e i om hast va j nafar davtalab
// val[i][j] = SIGMA z : C(sz[i], z + 1) * C(j, z);
for(int z = 0; z + 1 <= szb[i] && z <= j; z++)
val[i][j] = (val[i][j] + ll(ent2[i][z + 1]) * ent[j][z]) % mod;
assert(val[i][j] == 1);
}
ansbl[0] = 1;
for(int i = 0; i < n; i++){
for(int j = l[i] + 1; j <= r[i]; j++){
for(int k = 0; k < j; k++)
ansel[i][j] = (ansel[i][j] + ansbl[k] * ll(szb[j])) % mod;
if(i == 0)
continue;
int num = l[i - 1] < j && j <= r[i - 1];
for(int k = i - 2; k >= 0; k--){
//cout << "aha " << i << ' ' << j << ' ' << k << ' ' << num << ' ' << ansel[k][j - 1] << endl;
if(num)
ansel[i][j] = (ansel[i][j] + ll(ansel[k][j - 1]) * val[j][num]) % mod;
num += l[k] < j && j <= r[k];
}
}
for(int j = l[i] + 1; j <= r[i]; j++){
ansbl[j] = (ansbl[j] + ansel[i][j]) % mod;
//cout << i << ' ' << j << ' ' << ansel[i][j] << endl;
}
for(int j = 1; j < blsz; j++)
ansel[i][j] = (ansel[i][j - 1] + ansel[i][j]) % mod;
}
ll out = 0;
for(int i = 1; i < blsz; i++)
out += ansbl[i];
cout << out % mod << endl;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 1; i < exx.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
6548 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
6548 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
3264 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
6548 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
