Submission #1264617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264617		Alihan_8	Boat (APIO16_boat)	C++17	0 / 100	2 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;
}

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[i] <= p[i] && p[i + 1] <= b[i] + 1 ){
					int sum = 0, id = 0, binom = 1;
					
					for ( int k = j; k < n; k++ ){
						if ( a[k] <= p[i] && p[i + 1] <= b[k] + 1 ){
							id += 1;
							
							if ( id <= len ){
								binom = binom * 1LL * (len - id + 1) % Mod * inv[id] % Mod;
								
								add(sum, binom);
							}
							
							add(dp[i + 1][k + 1], dp[i][j] * 1LL * sum % 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