Submission #1264008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264008		altern23	Boat (APIO16_boat)	C++17	58 / 100	2003 ms	12336 KiB

boat

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e2;
const ll INF = 4e18;
const int MOD = 1e9 + 7;

int dp[MAXN + 5][1005], ps[MAXN + 5][1005];
ll comb[1005][MAXN + 5], inv[MAXN + 5], fc[MAXN + 5];
int A[MAXN + 5], B[MAXN + 5];
int prec[1005][MAXN + 5][2];

ll expo(ll a, ll b){
	ll ans = 1;
	for(;b > 0;){
		if(b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b /= 2;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	fc[0] = 1;
	for(int i = 1; i <= MAXN; i++){
		fc[i] = fc[i - 1] * i % MOD;
	}
	inv[MAXN] = expo(fc[MAXN], MOD - 2);
	for(int i = MAXN - 1; i >= 0; --i){
		inv[i] = inv[i + 1] * (i + 1) % MOD;
	}
	
	for(;tc--;){
		int N; cin >> N;
		
		vector<int> comp;
		comp.push_back(0);
		for(int i = 1; i <= N; i++){
			cin >> A[i] >> B[i];
			comp.push_back(A[i]), comp.push_back(B[i] + 1);
		}
		
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		
		auto get = [&](int idx){
			return lower_bound(comp.begin(), comp.end(), idx) - comp.begin() + 1;
		};
		
		dp[0][get(0)] = ps[0][get(0)] = 1;
		
		int M = comp.size();
		for(int i = 1; i <= M; i++) ps[0][i] += ps[0][i - 1];
		
		auto C = [&](int n, int r){
			if(n < 0 || r < 0 || n < r) return 0LL;
			return fc[n] * inv[r] % MOD * inv[n - r] % MOD;
		};
		
		comb[M][0] = comb[M][1] = 1;
		
		for(int i = 1; i <= M; i++){
			for(int j = 1; j <= N; j++){
				if(i < M){
					comb[M][0] = 1;
					if(comp[i] - comp[i - 1] < j) comb[i][j] = 0;
					else{
						int res = comp[i] - comp[i - 1], num = min(j, res - j);
						comb[i][j] = inv[num];
						for(int k = res; k > res - num; --k){
							comb[i][j] = comb[i][j] * k % MOD;
						}
					}
				}
				for(int k = 0; k <= j; k++){
					// 0 -> kalau start == end
					prec[i][j][0] = (prec[i][j][0] + C(j - 1, k - 1) * comb[i][k] % MOD);
					if(prec[i][j][0] >= MOD) prec[i][j][0] -= MOD;
					// 1 -> kalau start != end
					prec[i][j][1] = (prec[i][j][1] + C(j - 2, k - 2) * comb[i][k] % MOD);
					if(prec[i][j][1] >= MOD) prec[i][j][1] -= MOD;
				}
			}
		}
		
		for(int i = 1; i <= N; i++){
			A[i] = get(A[i]);
			B[i] = get(B[i] + 1) - 1;
			
			for(int j = 1; j <= M; j++){
				dp[i][j] = dp[i - 1][j];
				
				if(A[i] <= j && j <= B[i]){
					int cnt = 0;
					for(int k = i; k >= 1; --k){
						if(A[k] <= j && j <= B[k]){
							cnt++;
							if(k == i){
								dp[i][j] += 1LL * ps[k - 1][j - 1] * prec[j][cnt][0] % MOD;
								if(dp[i][j] >= MOD) dp[i][j] -= MOD;
							} 
							else{
								dp[i][j] += 1LL * ps[k - 1][j - 1] * prec[j][cnt][1] % MOD;
								if(dp[i][j] >= MOD) dp[i][j] -= MOD;
							}
						}
					}
				}	
				
				ps[i][j] = (ps[i][j - 1] + dp[i][j]);
				if(ps[i][j] >= MOD) ps[i][j] -= MOD;	
			}
		}
		
		// cout << dp[1][2] << "\n";
		cout << (ps[N][M] - 1LL + MOD) % MOD << "\n";
	}
}

/*
5 + 5 + 10 = 20?
*/

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