Submission #392126

#	Time	Username	Problem	Language	Result	Execution time	Memory
392126		soroush	Boat (APIO16_boat)	C++17	100 / 100	579 ms	4428 KiB

boat

//曇り空 のぞいた予感
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1010;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

vector < int > vec;
int n , m , inv[maxn];
int l[maxn] , r[maxn];
int dp[maxn][maxn*2];
int ans;

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i = 1 ; i < maxn ; i ++)inv[i] = pw(i , mod - 2);
	cin >> n;
	for(int i = 1 ; i <= n ; i ++)
		cin >> l[i] >> r[i] , r[i]++ , vec.pb(l[i]) , vec.pb(r[i]);
	sort(vec.begin() , vec.end());
	vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
	m = vec.size();
	for(int i = 0 ; i < m ; i ++)dp[0][i] = 1;
	for(int i = 1 ; i <= n ; i ++)
		l[i] = lower_bound(vec.begin() , vec.end() , l[i])-vec.begin()+1, 
		r[i] = lower_bound(vec.begin() , vec.end() , r[i])-vec.begin()+1;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = l[i] ; j < r[i] ; j ++){
			ll C = vec[j]-vec[j-1];
			ll x = vec[j]-vec[j-1], y = 1;
			for(int k = i-1 ; k >= 0 ; k --){
				dp[i][j] = (dp[i][j] + (dp[k][j-1] * 1ll * C)%mod)%mod;
				if(l[k] <= j and j < r[k]){
					x++ , ++y;
					C = (C * ((x * inv[y])%mod))%mod;
				}
			}	
		}
		for(int j = 0 ; j < m ; j ++)dp[i][j] = (dp[i][j] + dp[i][j-1])%mod;
		ans = (ans + dp[i][m-1])%mod;
	}
	cout << ans;
	return(0);
}

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