| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 533888 |
2022-03-07T14:51:17 Z |
new_acc |
Boat (APIO16_boat) |
C++14 |
|
904 ms |
20092 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e2+10;
const ll mod=1e9+7;
struct st{
int a,b,dl;
};
st pw[N*2];
ll dp[N][N*2];
ll dp2[N*2][N];
ll dp3[N*2][N];
pair<int,int>w[N];
ll sil[N],sp[N][N*2];
ll d1[N][N],d2[N*2][N];
ll power(ll n,ll k){
ll res=1;
while(k>0){
if(k&1) (res*=n)%=mod;
k>>=1;
(n*=n)%=mod;
}
return res;
}
ll dwu(ll n,ll k){
if(k>n) return 0;
ll curr=1;
for(int i=n;i>=n-k+1;i--) (curr*=(ll)i)%=mod;
return (curr*power(sil[k],mod-2))%mod;
}
void solve(){
int n;
cin>>n;
vi v;
for(int i=1;i<=n;i++){
cin>>w[i].fi>>w[i].se;
v.push_back(w[i].fi),v.push_back(w[i].se+1);
}
sort(v.begin(),v.end());
int l=0;
for(int i=0;i<v.size()-1;i++){
if(v[i]==v[i+1]) continue;
st pom;
pom.a=v[i],pom.b=v[i+1]-1,pom.dl=(pom.b-pom.a+1);
pw[++l]=pom;
}
sil[0]=1;
for(int i=1;i<=n;i++) (sil[i]=sil[i-1]*(ll)i)%=mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) d1[i][j]=dwu(i,j);
for(int i=1;i<=l;i++)
for(int j=1;j<=n;j++) d2[i][j]=dwu(pw[i].dl,j);
for(int i=1;i<=l;i++){
for(int j=1;j<=n;j++){
dp2[i][j]=pw[i].dl;
for(int k=min(j,pw[i].dl);k>=2;k--) (dp2[i][j]+=d1[j-1][k-1]*d2[i][k])%=mod;
}
}
for(int i=1;i<=l;i++){
for(int j=2;j<=n;j++){
if(pw[i].dl==1) continue;
dp3[i][j]=(ll)(pw[i].dl*(pw[i].dl-1LL))/2;
dp3[i][j]%=mod;
for(int k=min(j,pw[i].dl);k>=3;k--) (dp3[i][j]+=d1[j-2][k-2]*d2[i][k])%=mod;
}
}
ll res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=l;j++){
if(pw[j].b<w[i].fi or pw[j].a>w[i].se) continue;
dp[i][j]=pw[j].dl;
int il=1;
for(int k=i-1;k>=1;k--){
(dp[i][j]+=sp[k][j-1]*dp2[j][il])%=mod;
if(pw[j].a>=w[k].fi and pw[j].b<=w[k].se){
il++;
(dp[i][j]+=dp3[j][il])%=mod;
}
}
res+=dp[i][j];
}
for(int j=1;j<=l;j++) sp[i][j]=(sp[i][j-1]+dp[i][j])%mod;
}
cout<<res<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
Compilation message
boat.cpp: In function 'void solve()':
boat.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<v.size()-1;i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
904 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
904 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
4172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
904 ms |
20092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
