Submission #1288800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288800		Jawad_Akbar_JJ	Boat (APIO16_boat)	C++20	0 / 100	20 ms	10340 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], 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<=cur;i++){
		for (int m=0;m<=n;m++){
			int ch1 = 1, ch2 = 1;
			for (int j=0;j<=min(m, Sz[cur] - 1);j++){

				ch1 = ch1 * (Sz[i] - j) % mod * inv[j + 1] % mod;
				ways[i][m] = (ways[i][m] + ch1 * ch2) % mod;
				ch2 = ch2 * (m - j) % mod * inv[j + 1] % 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<<'\n';
}

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