Submission #673407

#	Time	Username	Problem	Language	Result	Execution time	Memory
673407		S2speed	Boat (APIO16_boat)	C++17	100 / 100	504 ms	16252 KiB

boat

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 1e3 + 17 , md = 1e9 + 7;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll l[maxn] , r[maxn] , w[maxn] , f[maxn][maxn] , dp[maxn][maxn];
vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n;
	cin>>n;
	for(ll i = 0 ; i < n ; i++){
		cin>>l[i]>>r[i]; l[i]--;
		v.push_back(l[i]); v.push_back(r[i]);
	}
	sort(all(v));
	v.resize(distance(v.begin() , unique(all(v))));
	ll vs = sze(v);
	for(ll i = 0 ; i < vs - 1 ; i++){
		w[i] = v[i + 1] - v[i];
		ll lm = min(w[i] , n);
		for(ll j = 1 ; j <= lm ; j++){
			f[i][j] = (w[i] - j + 1) * tav(j , md - 2) % md;
		}
	}
	for(ll i = 0 ; i < n ; i++){
		l[i] = lower_bound(all(v) , l[i]) - v.begin();
		r[i] = lower_bound(all(v) , r[i]) - v.begin();
	}
	for(ll i = 0 ; i < vs - 1 ; i++) dp[i][0] = 1;
	for(ll i = 0 ; i < n ; i++){
		for(ll j = r[i] - 1 ; j >= l[i] ; j--){
			ll h = 0 , lm = min(i + 1 , w[j]);
			for(ll k = lm ; k ; k--){
				ll o = dp[j][k - 1] * f[j][k] % md;
				dp[j][k] += o; dp[j][k] -= (dp[j][k] >= md) * md;
				h += o;
			}
			for(ll k = j + 1 ; k < vs ; k++){
				dp[k][0] += h; dp[k][0] %= md;
			}
		}
	}
	ll ans = dp[vs - 1][0];
	cout<<ans<<'\n';
	return 0;
}

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