Submission #270583

#	Time	Username	Problem	Language	Result	Execution time	Memory
270583		test2	Boat (APIO16_boat)	C++14	100 / 100	654 ms	10352 KiB

boat

#include<bits/stdc++.h>

#define I inline void 

using ll = long long ; 
using ld = long double ; 

using namespace std ; 

const int N = 1e6 + 7 , mod = 1e9+7 ;  

// how interesting!

int n , m; 
vector<int> lst ; 
int L[N] , R[N] , S[N] ; 
int dp[1001][501] ;

ll faspow(ll x , ll y){
	if(!y)return 1ll ; 
	ll ret = faspow(x , y/2) ; 
	ret = 1ll * ret *ret %mod ;
	if(y&1)ret = 1ll * ret * x %mod ;
	return ret ; 
}

ll inv[N] ; 

int main(){	
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in" , "r" , stdin) ;  
	inv[1] = 1ll ; 
	for(int i = 2; i < N; i++) inv[i] = (mod/i) * (mod-inv[mod%i]) % mod;

		cin >> n ; 
	for(int i = 1 ;i <= n;i++){
		cin >> L[i] >> R[i] ; 
		R[i] ++ ;
		lst.push_back(L[i]) ; 
		lst.push_back(R[i]) ;
	}
	sort(lst.begin() , lst.end()) ; 
	lst.resize(unique(lst.begin() , lst.end()) - lst.begin()) ; 


	for(int i = 1 ;i <= n ;i++){
		L[i] = lower_bound(lst.begin() , lst.end() , L[i]) - lst.begin() + 1; 
		R[i] = lower_bound(lst.begin() , lst.end() , R[i]) - lst.begin() + 1;
	}

	int w = lst.size() ; 
	for(int i = 1 ;i < w ;i++){
		S[i] = lst[i] - lst[i-1] ; 
	}

	dp[0][0] = 1ll ;
	for(int i = 1 ;i < w ;i++){
		dp[i][0] = 1ll ; 

		for(int j = 1 ;j <=n ;j++){
			int count = 1; 
			ll mul = S[i] ; 

			dp[i][j] = dp[i-1][j] ; 

			if(i < L[j] || i >= R[j])
				continue ; 

			for(int k = j -1 ; k >= 0 ; k --){
				dp[i][j] = (dp[i][j] + (mul * dp[i-1][k]) %mod  ) %mod ; 
				if(L[k] <= i && R[k] > i){

					mul = 1ll * mul * (S[i] + count) %mod ; 
					mul = 1ll * mul * inv[count +1] %mod ; 

					count ++ ;
				}	
			}
		}
	}


	ll ans = 0ll ; 
	for(int i = 1 ; i<=n ;i++){
		ans = (ans + dp[w-1][i]) %mod ; 
	}
	cout<< ans ; 
	return 0 ; 
}

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