제출 #1264642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264642		Alihan_8	Boat (APIO16_boat)	C++17	0 / 100	325 ms	1344 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

void add(int &x, const int &y){
	x += y;
	
	if ( x >= Mod ) x -= Mod;
}

int inv[501];

int binPow(int x, int y){
	int res = 1;
	
	for (; y > 0; x = x * 1LL * x % Mod, y >>= 1 ){
		if ( y & 1 ) res = res * 1LL * x % Mod;
	}
	
	return res;
}

int bin(int n, int k){
	if ( n < k ) return 0;
	
	int res = 1;
	
	for ( int i = n - k + 1; i <= n; i++ ) res = res * 1LL * i % Mod;
	for ( int i = 1; i <= k; i++ ) res = res * 1LL * inv[i] % Mod;
	
	return res;
}

signed main(){
	for ( int i = 0; i <= 500; i++ ) inv[i] = binPow(i, Mod - 2);
	
	int n; cin >> n;
	
	vector <int> a(n), b(n), p;
	
	for ( int i = 0; i < n; i++ ){
		cin >> a[i] >> b[i];
		
		p.push_back(a[i]);
		p.push_back(b[i]);
	}
	
	sort(begin(p), end(p));
	p.resize(unique(begin(p), end(p)) - begin(p));
	
	int m = size(p);
	
	vector <vector<int>> dp(m, vector <int> (n + 1));
	
	dp[0][0] = 1;
	
	for ( int i = 0; i + 1 < m; i++ ){
		int len = p[i + 1] - p[i];
		
		for ( int j = 0; j <= n; j++ ){
			add(dp[i + 1][j], dp[i][j]);
			
			if ( j + 1 <= n ){
				add(dp[i][j + 1], dp[i][j]);
				
				if ( a[j] <= p[i] && p[i + 1] <= b[j] + 1 ){
					add(dp[i + 1][j + 1], dp[i][j] * 1LL * len % Mod);
					
					int sum = 0, id = 0, binom = len - 1;	
					
					for ( int k = j + 1; k < n; k++ ){
						if ( a[k] <= p[i] && p[i + 1] <= b[k] + 1 ){
							id += 1;
							
							int cur = 0;
							
							for ( int t = 1; t <= min(len - 1, id); t++ ){	
								add(cur, bin(id - 1, t - 1) * 1LL * bin(len, t + 1) % Mod);
							}
							
							add(dp[i + 1][k + 1], dp[i][j] * 1LL * cur % Mod);
						}
					}
				}
			}
		}
	}
	
	cout << (dp[m - 1][n] - 1 + Mod) % Mod << '\n';
}

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