Submission #533888

#	Time	Username	Problem	Language	Result	Execution time	Memory
533888		new_acc	Boat (APIO16_boat)	C++14	0 / 100	904 ms	20092 KiB

boat

#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 (stderr)

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++){
      |              ~^~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42