| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 200580 |
2020-02-07T12:51:57 Z |
red1108 |
Boat (APIO16_boat) |
C++17 |
|
19 ms |
12280 KB |
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e16;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl <<endl;}
int in[510][2], n;
vector<int> h;
int cnt[1010];
ll dp[510][1010],mod=1e9+7,ncr[510][510],choice[1010][510],iinv[510],ndr[1010][510];
ll mypow(ll a, ll b){
ll ret=1;
while(b){
if(b&1) ret = ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
int main(){
fastio;
cin>>n;
h.eb(0);
for(int i=1;i<=n;i++){
cin>>in[i][0]>>in[i][1];in[i][1]++;
h.eb(in[i][0]);h.eb(in[i][1]);
}
ncr[0][0]=1;
for(int i=1;i<=n;i++){
ncr[i][0]=1;
for(int j=1;j<=i;j++) ncr[i][j]=(ncr[i-1][j-1]+ncr[i-1][j])%mod;
}
for(int i=1;i<=n;i++) iinv[i]=mypow(i,mod-2);
sort(h.begin(),h.end());
h.resize(unique(all(h))-h.begin());
for(int i=1;i<=n;i++){
in[i][0]=lower_bound(all(h),in[i][0])-h.begin();
in[i][1]=lower_bound(all(h),in[i][1])-h.begin();
for(int j=in[i][0];j<in[i][1];j++) cnt[j]++;
}
for(int j=1;j<h.size()-1;j++){
ll m = h[j+1]-h[j], c = 1;
ndr[j][0]=1;
for(int i=1;i<=n;i++){
if(i>m) break;
c = c * (m-i+1)%mod * iinv[i]%mod;
ndr[j][i]=c;
}
}
for(int j=1;j<h.size()-1;j++){
choice[j][1]=h[j+1]-h[j];
for(int s=2;s<=cnt[j];s++){
choice[j][s]=choice[j][s-1];
for(int i=2;i<=s;i++)
choice[j][s] = (choice[j][s] + ndr[j][i] * ncr[s-2][i-2] ) %mod;
}
}
ll ans=0;
for(int i=0;i<=2*n;i++) dp[0][i]=1;
for(int i=1;i<=n;i++){
if(i==1){
for(int j=in[i][0];j<in[i][1];j++) dp[i][j]=dp[i][j-1]+h[j+1]-h[j];
continue;
}
for(int j=in[i][0];j<in[i][1];j++){
dp[i][j]=dp[i][j-1];
int num=0;
for(int k=i;k>=1;k--){
if(in[k][0]<=j&&j<in[k][1]) num++;
dp[i][j]=(dp[i][j]+dp[k-1][j-1]*choice[j][num]%mod)%mod;
}
}
}
for(int i=1;i<=n;i++){
ans = (ans + dp[i][in[i][1]-1])%mod;
}
cout<<ans;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<h.size()-1;j++){
~^~~~~~~~~~~
boat.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<h.size()-1;j++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
