Submission #1340930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340930		javkhlantogs	Boat (APIO16_boat)	C++20	100 / 100	769 ms	4384 KiB

boat

#include<bits/stdc++.h>                                               
#define ll long long                                                    
using namespace std;                                                     
ll mod=1e9+7;
ll powr(ll a,ll b){
	if(b==0) return 1;
	ll v=powr(a,b/2);
	v=(v*v)%mod;
	if(b%2) v=(v*a)%mod;
	return v;
}                                                                                                                    
int main(){                                                                              
	ll n,i,j,k,q;                                                                       
	cin>>n;                                                                                
	vector<ll> a(n+1),b(n+1),p,inv(n+1);
	for(i=1 ; i<=n ; i++) inv[i]=powr(i,mod-2);
	for(i=1 ; i<=n ; i++) cin>>a[i]>>b[i];
	for(i=1 ; i<=n ; i++){ 
		p.push_back(a[i]);
		p.push_back(b[i]+1);
	}   
	sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end());
	ll m=p.size();
	vector<vector<ll>> dp(n+1,vector<ll>(m,0));
	vector<ll> pre(n+1,0);
	pre[0]=1;
	for(i=0 ; i<m-1 ; i++){
		ll l=p[i+1]-p[i];
		for(j=1 ; j<=n ; j++){
			if(a[j]<=p[i] and p[i+1]-1<=b[j]){
				ll cnt=1,val=l;
				for(k=j-1 ; k>=0 ; k--){
					dp[j][i]=(dp[j][i]+pre[k]*val)%mod;
					if(a[k]<=p[i] and p[i+1]-1<=b[k]){
						cnt++;
						val=(((val*(l+cnt-1))%mod)*inv[cnt])%mod;
					}
				}
			}
		}
		for(j=1 ; j<=n ; j++) pre[j]=(pre[j]+dp[j][i])%mod;
	}
	ll ans=0;
	for(i=1 ; i<=n ; i++) ans=(ans+pre[i])%mod;
	cout<<ans;
	return 0;
}                                                                         

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