#473916 (C++14) No.1043 直列大学

• 問題: No.1043 直列大学
• ユーザー: QCFium
• 提出日時: 2020-05-01 21:37:35
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,031 bytes
• コンパイル時間: 1,937 ms
• コンパイル使用メモリ: 167,116 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-07 02:46:51
• 合計ジャッジ時間: 3,509 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 5,248 KB
testcase_01	AC	4 ms; 5,376 KB
testcase_02	AC	4 ms; 5,376 KB
testcase_03	AC	4 ms; 5,376 KB
testcase_04	AC	4 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	4 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	27 ms; 5,376 KB
testcase_13	WA	-
testcase_14	AC	23 ms; 5,376 KB
testcase_15	AC	26 ms; 5,376 KB
testcase_16	AC	23 ms; 5,376 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	WA	-
testcase_19	AC	23 ms; 5,376 KB
testcase_20	AC	17 ms; 5,376 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	12 ms; 5,376 KB
testcase_28	AC	22 ms; 5,376 KB
testcase_29	AC	9 ms; 5,376 KB
testcase_30	AC	20 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
#define MOD 1000000007
int main() {
	int n = ri(), m = ri();
	int a[n], b[m];
	for (auto &i : a) i = ri();
	for (auto &i : b) i = ri();
	int x = ri(), y = ri();
	int dp0[100001];
	memset(dp0, 0, sizeof(dp0));
	dp0[0] = 1;
	auto add = [&] (int &a, int b) {
		a += b;
		if (a >= MOD) a -= MOD;
	};
	for (auto i : a) for (int j = 100000 - i; j >= 0; j--) add(dp0[j + i], dp0[j]);
	int dp1[100001];
	memset(dp1, 0, sizeof(dp1));
	dp1[0] = 1;
	for (auto i : b) for (int j = 100000 - i; j >= 0; j--) add(dp1[j + i], dp1[j]);
	
	dp0[0] = dp1[0] = 0;
	
	int sum[100002];
	memset(sum, 0, sizeof(sum));
	for (int i = 0; i <= 100000; i++) sum[i + 1] = sum[i], add(sum[i + 1], dp0[i]);
	
	int res = 0;
	for (int i = 0; i <= 100000; i++) {
		int64_t lower = (int64_t) i * x;
		int64_t upper = std::min<int64_t>((int64_t) i * y + 1, 100001);
		if (lower <= 100000) add(res, (int64_t) (sum[upper] - sum[lower]) * dp1[i] % MOD);
	}
	printf("%d\n", res);
	
	return 0;
}