# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47974 | 3zp | Boat (APIO16_boat) | C++14 | 40 ms | 9212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5009], b[5009];
ll mod = 1e9+7;
ll c[2009];
ll l[5009], r[5009];
ll dp[5009][4009];
ll in[5009];
vector<pair<ll,ll> > d;
main(){
ll n;
cin >> n;
for(ll i = 0; i < n; i++){
cin >> a[i] >> b[i];
c[2*i] = a[i];
c[2*i + 1] = b[i];
}
sort(c, c+2*n);
in[0] = 1;
in[1] = 1;
for (ll i = 2; i <= n; i++)
in[i] = in[mod % i] *(mod - mod / i) % mod;
for(ll i = 0; i < 2*n; i++){
if(i < 2*n-1 && c[i] == c[i+1]) continue;
d.push_back({c[i], c[i]});
if(i == 2*n-1 || c[i+1] == c[i]+1) continue;
d.push_back({c[i]+1, c[i+1]-1});
}
for (ll i= 0; i < n; i++){
for (ll j = 0; j < d.size(); j++){
if(a[i] == d[j].first) {l[i] = j; break;}
}
for (ll j = 0; j < d.size(); j++){
if(b[i] == d[j].second) r[i] = j;
}
}
ll N = d.size();
for(ll i = 0; i < n; i++){
for(ll j = 0; j < N; j++){
if(j) dp[i][j] = (dp[i][j-1]);
ll L = d[j].second - d[j].first + 1;
ll W = 1;
for (ll t = i; t >= 0; t--){
if(l[t] > j || r[t] < j) break;
W = (W*(L - (i -t)) % mod )*in[i-t+1] % mod;
if(!W) break;
if(t == 0) dp[i][j] = (dp[i][j] + W) % mod; else
if(j == 0) dp[i][j] = (dp[i][j] + W) % mod; else
dp[i][j] = (dp[i][j] + W*dp[t-1][j-1]) % mod;
}
}
for(ll j = 0; j < N; j++){
if(i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
else dp[i][j] = (dp[i][j] + 1) % mod;
}
}
cout << (dp[n-1][N-1] -1 + mod)% mod << endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |