Submission #20746

#	Time	Username	Problem	Language	Result	Execution time	Memory
20746		ainu7	복불복 (OJUZ11_luck)	C++11	100 / 100	533 ms	2024 KiB

luck

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mmod = 1000000007;

int calc(vector<int> a, vector<int> b, int k, int ue, int le) {
	int n = a.size();
	vector<int> cnt(n);

	for (int i=0; i<k; i++)
		for (int j=0; j<n; j++)
			if (a[i]+b[j] >= ue) cnt[i] = j+1;
	for (int i=k; i<n; i++)
		for (int j=0; j<n; j++)
			if (a[i]+b[j] > le) cnt[i] = j+1;

	vector<int> prv(n+1);
	prv[0] = 1;
	if (k % 2) prv[0] = -1;

	for (int i=n-1; i>=0; i--) {
		vector<int> nxt(n+1);
		for (int j=0; j<n; j++) {
			int mult = max(0, cnt[i] - j);
			nxt[j+1] = (nxt[j+1] - 1LL * mult * prv[j]) % mmod;
			if (i >= k) {
				nxt[j] = (nxt[j] + prv[j]) % mmod;
			}
		}
		for (int j=0; j<=n; j++)
			prv[j] = (nxt[j] + mmod) % mmod;
	}

	int ret = 0;
	for (int i=0; i<=n; i++) {
		int now = prv[i];
		for (int j=1; j<=n-i; j++)
			now = (now * 1LL * j) % mmod;
		ret = (ret + now) % mmod;
	}
	return ret;
}

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	for (int i=0; i<n; i++) cin >> a[i];
	for (int i=0; i<n; i++) cin >> b[i];

	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());

	int res = 0;
	for (int x = 1; x <= 2000; x++) {
		res += calc(a, b, k, x, x);
		res -= calc(a, b, k, x+1, x);
		res %= mmod;
		res = (res + mmod) % mmod;
	}
	cout << res << endl;
}

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