Submission #1319379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319379		nguyenkhangninh99	Boat (APIO16_boat)	C++20	100 / 100	731 ms	15972 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e3 + 5, mod = 1e9 + 7;
int dp[maxn][maxn], pre[maxn][maxn],sum_dp[maxn],val[2*maxn],L[maxn],R[maxn],inv[maxn];
int binpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res  =res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
   
   // freopen("BOAT.inp", "r", stdin);
   // freopen("BOAT.out", "w", stdout);
	int n; cin >> n;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cin >> L[i] >> R[i];
		val[++cnt] = L[i];
		val[++cnt] = R[i] + 1;
	}
	sort(val + 1, val + cnt + 1);
	cnt = unique(val + 1, val + cnt + 1) - (val + 1);
	for(int i = 1; i <= n; i++) inv[i] = binpow(i, mod - 2);
	for(int i = 0; i <= cnt; i++) sum_dp[i] = 1;

	for(int i = 1; i <= n; i++){
		int idl = lower_bound(val + 1, val + cnt + 1, L[i]) - val;
		int idr = lower_bound(val + 1, val + cnt + 1, R[i] + 1) - val;
		
		for(int j = idl; j < idr; j++)
			for(int k = 1; k <= i; k++) pre[j][k] = dp[j][k];

		for(int j = idl; j < idr; j++){
			int len = (val[j + 1] - val[j]);
			dp[j][1] = (dp[j][1] + sum_dp[j-1] * len) % mod; //k = 1
			for(int k = 2; k <= i; k++){ //k > 1
				dp[j][k] = (dp[j][k] + pre[j][k - 1] * (len - k + 1) % mod * inv[k] % mod) % mod;
			}
		}

		for(int j = 1; j < cnt; j++){
            sum_dp[j] = sum_dp[j - 1];
			for(int k = 1; k <= i; k++) sum_dp[j] = (sum_dp[j] + dp[j][k]) % mod;
		}
	}

	int ans = 0;
	for(int j = 1; j < cnt; j++){
		for(int k = 1; k <= n; k++) ans = (ans + dp[j][k]) % mod;
    }
	cout << ans;
}

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