Submission #20753

#	Time	Username	Problem	Language	Result	Execution time	Memory
20753		gs12117	복불복 (OJUZ11_luck)	C++11	100 / 100	209 ms	1124 KiB

luck

#include<cstdio>
#include<algorithm>
const int mod = 1000000007;
int a[110];
int b[110];
int c[110];
int d[110];
long long int dp[110];
long long int ndp[110];
long long int calc(int n, int m, int x) {
	int p = 0;
	int q = m;
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		while (p < m&&c[p] + d[n - i - 1] < x) {
			p++;
			dp[p] = 0;
		}
		while (q < n&&c[q] + d[n - i - 1] < x) {
			for (int j = 0; j <= p; j++) {
				dp[j] *= i - j - q + m;
				dp[j] %= mod;
			}
			q++;
		}
		for (int j = 0; j <= p; j++) {
			ndp[j] = dp[j];
		}
		for (int j = 0; j < p; j++) {
			ndp[j + 1] += dp[j] * (p - j);
		}
		for (int j = 0; j <= p; j++) {
			dp[j] = ndp[j] % mod;
		}
	}
	while (p < m) {
		p++;
		dp[p] = 0;
	}
	while (q < n) {
		for (int j = 0; j <= p; j++) {
			dp[j] *= n - j - q + m;
			dp[j] %= mod;
		}
		q++;
	}
	return dp[m];
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &b[i]);
	}
	std::sort(a, a + n);
	std::sort(b, b + n);
	m = n - m;
	for (int i = 0; i < n; i++) {
		a[i] *= n;
		a[i] += i;
		b[i] *= n;
	}
	long long int ans = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			int x = a[i] + b[j];
			int cn = 0;
			int dn = 0;
			for (int k = 0; k < n; k++) {
				if (k != i) {
					c[cn] = a[k];
					cn++;
				}
				if (k != j) {
					d[dn] = b[k];
					dn++;
				}
			}
			ans += calc(n - 1, m - 1, x);
			ans %= mod;
		}
	}
	if (m == 0) {
		ans = 1;
		for (int i = 1; i <= n; i++) {
			ans *= i;
			ans %= mod;
		}
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

luck.cpp: In function 'int main()':
luck.cpp:51:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
luck.cpp:53:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
luck.cpp:56:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);
                     ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27