제출 #455011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
455011		nonsensenonsense1	Boat (APIO16_boat)	C++17	100 / 100	698 ms	4372 KiB

boat

#include <cstdio>
#include <algorithm>

const int md = 1000000007;

inline int add(int a, int b) 
{
	a += b;
	if (a >= md) a -= md;
	return a;
}
inline int sub(int a, int b) 
{
	a -= b;
	if (a < 0) a += md;
	return a;
}
inline int mul(int a, int b) 
{
	return (long long)a * b % md;
}
int po(int a, int b) 
{
	int r = 1;
	while (b) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}
inline int inv(int a) 
{
	return po(a, md - 2);
}
inline int di(int a, int b) 
{
	return mul(a, inv(b));
}

const int N = 505;
int n, d[N << 1], l[N], r[N], a[N << 1], p[N << 1][N], amt[N << 1], ncr[N << 1][N];

int main() 
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", l + i, r + i);
		a[i << 1] = l[i];
		a[i << 1 | 1] = r[i] + 1;
	}
	std::sort(a, a + n * 2);
	int len = std::unique(a, a + n * 2) - a;
	d[0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = len - 1; j >= 1; --j) if (l[i] <= a[j - 1] && r[i] >= a[j] - 1) {
			if (!amt[j]) ncr[j][0] = a[j] - a[j - 1];
			else ncr[j][amt[j]] = di(mul(ncr[j][amt[j] - 1], ncr[j][0] - amt[j]), amt[j] + 1);
			for (int k = amt[j]; k > 0; --k) {
				p[j][k] = add(p[j][k], p[j][k - 1]);
				d[j] = add(d[j], mul(p[j][k - 1], ncr[j][k]));
			}
			for (int k = 0; k < j; ++k) {
				p[j][0] = add(p[j][0], d[k]);
				d[j] = add(d[j], mul(ncr[j][0], d[k]));
			}
			++amt[j];
		}
	}
	int ans = 0;
	for (int i = 1; i < len; ++i) ans = add(ans, d[i]);
	printf("%d\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", l + i, r + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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