제출 #1288813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288813		Jawad_Akbar_JJ	Boat (APIO16_boat)	C++20	100 / 100	1075 ms	12460 KiB

boat

#include <iostream>
#include <map>

using namespace std;
#define int long long
const int N = 505;
int l[N], r[N], Sz[N<<2], cur, dp[N][N<<2], ways[N<<2][N], Chs[N][N], Num1[N], inv[N], mod = 1e9 + 7;
map<int, int> mp, mp2;

int power(int a, int b){
	if (b == 1)
		return a;
	int ans = power(a, b / 2);
	ans = ans * ans % mod;
	if (b % 2)
		ans = ans * a % mod;
	return ans;
}

signed main(){
	for (int i=1;i<N;i++)
		inv[i] = power(i, mod - 2);

	int n, lst = -1, Ans = 0;
	cin>>n;

	for (int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		mp[l[i] - 1];
		mp[r[i]];
	}

	for (auto [i, j] : mp){
		mp2[i] = ++cur;
		if (lst == -1)
			Sz[cur] = 1;
		else
			Sz[cur] = i - lst;
		lst = i;
	}


	for (int i=1;i<=n;i++){
		l[i] = mp2[l[i] - 1] + 1;
		r[i] = mp2[r[i]];
	}

	for (int i=1;i<N;i++){
		for (int j=Chs[i-1][0]=1;j<N;j++)
			Chs[i][j] = (Chs[i-1][j-1] + Chs[i-1][j]) % mod;
	}

	for (int i=1;i<=cur;i++){
		int ch = 1;
		for (int j=0;j<=n;j++)
			Num1[j] = ch = ch * (Sz[i] - j) % mod * inv[j + 1] % mod;

		for (int m=0;m<=n;m++){
			for (int j=0;j<=min(m, Sz[i] - 1);j++)
				ways[i][m] = (ways[i][m] + Num1[j] * Chs[m][j]) % mod;
		}
	}

	for (int j=0;j<=cur;j++)
		dp[0][j] = 1;
	
	for (int i=1;i<=n;i++){
		for (int cr=l[i];cr <= r[i];cr++){
			int m = 0;
			for (int j=i-1;j>=0;j--){
				dp[i][cr] = (dp[i][cr] + dp[j][cr - 1] * ways[cr][m]) % mod;
				m += (cr >= l[j] and cr <= r[j]);
			}

			Ans += dp[i][cr];
		}

		for (int j=1;j<=cur;j++)
			dp[i][j] = (dp[i][j-1] + dp[i][j]) % mod;
	}
	cout<<Ans % mod<<'\n';
}

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