제출 #1303379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303379		fuyu	Boat (APIO16_boat)	C++20	9 / 100	4 ms	2376 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 maxR[maxn << 1];
int dp[maxn][maxn << 1];
vector<int> com;
priority_queue<int, vector<int>> pq;

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]);
	}

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

	for(int i = 1; i <= n; ++i)
		maximize(maxR[getID(a[i])], b[i]);

	int SIZE = com.size();

	for(int i = 1; i <= SIZE; ++i){
		int id = getID(com[i - 1]);

		if (maxR[id] != 0)
			pq.push(maxR[id]);

		if (pq.size() && (int)pq.top() > com[i - 1])
			L[i] = com[i - 1], R[i] = com[i] - 1;
		else
			L[i] = 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;
		for(int j = 1; j <= SIZE; ++j){
			dp[i][j] = dp[i - 1][j]; //Khong chon i
			add(dp[i][j],
				dp[i][j - 1]); //Ghep i vao nhung doan nho hon
			sub(dp[i][j],
				dp[i - 1][j - 1]);

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

			for(int pre = i; pre >= 1; --pre){
				if ((i - pre + 1) > (R[j] - L[j] + 1))
					break;

				if (L[j] < a[pre] || R[j] > b[pre])
					break;

				//C(len, cnt) = (len - cnt + 1)...len/cnt!
				//S(len, cnt) = sigma(C(len, x) * C(cnt, x)) = C(len + cnt, cnt)
				//  = (len + 1)...(len + cnt)/cnt!


				if (dp[pre - 1][j - 1] == 0)
					continue;

				int total = mul(way, fiv[i - pre]);

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

				way = mul(way, len + i - pre + 1);
			}
		}
	}

	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;
}

컴파일 시 표준 에러 (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: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42