Submission #1303434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303434		fuyu	Boat (APIO16_boat)	C++20	100 / 100	258 ms	2444 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ins insert
#define fi first
#define se second
#define ld long double
#define ALL(x) (x).begin(), (x).end()
#define MASK(x) (1ULL << (x))
#define BIT(x, k) ((x) >> (k) & 1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

template<typename T1, typename T2> bool maximize(T1 &x, const T2 &y){
	if (x < y){
		x = y;
		return 1;
	}
	return 0;
}

template<typename T1, typename T2> bool minimize(T1 &x, const T2 &y){
	if (x > y){
		x = y;
		return 1;
	}
	return 0;
}

bool ST_ALLOC;

#define file "BOAT"

void fastio(){
	if (fopen(file".INP", "r")){
		freopen(file".INP", "r", stdin);
		freopen(file".OUT", "w", stdout);
	}
}

const int maxn = 5e2 + 9;
const int mod = 1e9 + 7;

void add(int &a, const int &b){
	a += b;

	if (a >= mod)
		a -= mod;
}

void sub(int &a, const int &b){
	a -= b;
	if (a < 0)
		a += mod;
}

int mul(const int &a, const int &b){
	return (1ll * a * b) % mod;
}

int binpow(int a, int b){
	int res = 1;

	while (b > 0){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int n;
int a[maxn];
int b[maxn];
int fiv[maxn];
int fact[maxn];
int L[maxn << 1];
int R[maxn << 1];
int dp[maxn][maxn << 1];
vector<int> com;

int getID(int val){
	return lower_bound(ALL(com), val) - com.begin() + 1;
}

bool EN_ALLOC;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	fastio();

	cin >> n;

	for(int i = 1; i <= n; ++i){
		cin >> a[i] >> b[i];
		com.pb(a[i]);
		com.pb(b[i] + 1);
	}

	sort(ALL(com));
	com.erase(unique(ALL(com)), com.end());

	int SIZE = com.size() - 1;

	for(int i = 1; i <= SIZE; ++i){
		L[i] = com[i - 1];
		R[i] = com[i] - 1;
	}

	fact[0] = fiv[0] = 1;
	for(int i = 1; i <= n; ++i)
		fact[i] = (1ll * fact[i - 1] * i) % mod;
	fiv[n] = binpow(fact[n], mod - 2);
	for(int i = n - 1; i >= 1; --i)
		fiv[i] = (1ll * (i + 1) * fiv[i + 1]) % mod;

	for(int i = 0; i <= SIZE; ++i)
		dp[0][i] = 1;

	for(int i = 1; i <= n; ++i){
		dp[i][0] = 1; //Khong ghep vao doan nao
		for(int j = 1; j <= SIZE; ++j){
			int &ans = dp[i][j];

			ans = dp[i - 1][j]; //Khong chon i

			if (j >= 2){
				add(ans,
					dp[i][j - 1]); //Ghep i vao nhung doan nho hon
				sub(ans,
					dp[i - 1][j - 1]);
			}

			if (L[j] < a[i] || R[j] > b[i])
				continue;

			int len = R[j] - L[j] + 1;
			int way = 1;
			int cnt = 0;

			for(int pre = i; pre >= 1; --pre){
				if (L[j] < a[pre] || R[j] > b[pre])
					continue;
				/*
				S(len, cnt) = C(len + cnt - 2, cnt) = (len - 1)...(len + cnt - 2)/cnt!
				*/

				++cnt;

				int total = len;

				way = mul(way, len + cnt - 2);

				if (pre < i)
					total = mul(way, fiv[cnt]);

				add(ans,
					mul(dp[pre - 1][j - 1], total));
			}
		}
	}

	cout << (dp[n][SIZE] - 1 + mod) % mod << '\n';

	cerr << "Time ran : " << TIME << "s\n";
	cerr << "Static memory used : " << fixed << setprecision(2) << (((&EN_ALLOC) - (&ST_ALLOC)) / (1.0l * 1024 * 1024)) << "mb\n";
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void fastio()':
boat.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(file".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:39:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |                 freopen(file".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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