Submission #261992

#	Time	Username	Problem	Language	Result	Execution time	Memory
261992		amoo_safar	Boat (APIO16_boat)	C++17	100 / 100	1944 ms	4732 KiB

boat

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> edge;
typedef pair<int, int> pii;

const int Maxn = 1e3 + 10;
const int Inf = 1e9;
const int Log = 20;
const int Mod = 1e9 + 7;

int mul(int a, int b){
	return (1ll * a * b) % Mod;
}

int pw(int b, int p){
	if(p == 0) return 1;
	if(p & 1) return mul(b, pw(b, p - 1));
	return pw(mul(b, b), p >> 1);
}
int inv[Maxn * 4];

int a[Maxn], b[Maxn];
set<int> st;
vector<pii> V;

int dp[2][1040][510];
int sm[2][1040];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < 4 * Maxn; i++) inv[i] = pw(i, Mod - 2);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		b[i] ++;
		st.insert(a[i]);
		st.insert(b[i]);
		//assert(a[i] == b[i] - 1);
	}
	
	ll l = -1;
	for(auto x : st){
		if(l != -1) V.pb({l, x});
		l = x;
	}
	sort(all(V));
	int m = V.size();
	for(int I = 1; I <= n; I++){
		int II = I & 1;
		memset(dp[II], 0, sizeof dp[II]);
		memset(sm[II], 0, sizeof sm[II]);
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int cnt = 2; cnt <= I; cnt ++){
					//if(cnt > V[i].S - V[i].F) continue;
					dp[II][i][cnt] = mul( dp[II ^ 1][i][cnt - 1], mul((V[i].S - V[i].F) - cnt + 1, inv[cnt]) );
				}
			}
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int j = 0; j < i; j++){
					dp[II][i][1] += mul( sm[II ^ 1][j], V[i].S - V[i].F );
					if(dp[II][i][1] >= Mod)
						dp[II][i][1] %= Mod;
				}
			}
		}
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				dp[II][i][1] += (V[i].S - V[i].F);
				//S += (V[i].S - V[i].F);
				dp[II][i][1] %= Mod;
			}
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			dp[II][i][cnt] += dp[II ^ 1][i][cnt];
			if(dp[II][i][cnt] >= Mod)
				dp[II][i][cnt] -= Mod;
			
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			sm[II][i] += dp[II][i][cnt];
			//cerr << I << " " << dp[II][i][cnt] << "\n";
			//sm[II][i] %= Mod;
			if(sm[II][i] >= Mod)
				sm[II][i] -= Mod;
		}
	}
	
	ll ans = 0;
	for(int i = 0; i < m; i++) ans += sm[n & 1][i];
	cout << ((ans % Mod) + Mod) % Mod << '\n';
	return 0;
}

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