#368568 (C++14) No.868 ハイパー部分和問題

• 問題: No.868 ハイパー部分和問題
• ユーザー: e869120
• 提出日時: 2019-08-15 13:12:37
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 1,042 bytes
• コンパイル時間: 942 ms
• コンパイル使用メモリ: 79,432 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-21 18:10:08
• 合計ジャッジ時間: 26,324 ms
• ジャッジサーバーID （参考情報）: judge9 / judge10

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	2 ms; 4,348 KB
testcase_11	AC	2 ms; 4,348 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	1,693 ms; 4,348 KB
testcase_15	AC	1,690 ms; 4,348 KB
testcase_16	AC	1,692 ms; 4,348 KB
testcase_17	AC	1,692 ms; 4,348 KB
testcase_18	AC	1,690 ms; 4,348 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	1,368 ms; 4,348 KB
testcase_30	AC	1,363 ms; 4,348 KB
testcase_31	AC	1,375 ms; 4,348 KB
testcase_32	AC	1,684 ms; 4,348 KB
testcase_33	AC	1,679 ms; 4,348 KB
testcase_34	AC	1,781 ms; 4,348 KB
testcase_35	AC	1,781 ms; 4,348 KB
testcase_36	AC	1,140 ms; 4,348 KB
testcase_37	AC	1,138 ms; 4,348 KB
testcase_38	AC	2 ms; 4,348 KB
testcase_39	AC	2 ms; 4,348 KB

ソースコード

#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
using namespace std;

const int BACKET = 150;
int N, K, Q, A[15009], X[15009], V[15009], ans[15009];
bool used[15009];
bitset<15009>ZERO;

void query(int cl, int cr) {
	for (int i = 1; i <= N; i++) used[i] = false;
	vector<int> J;
	for (int i = cl; i <= cr; i++) { used[X[i]] = true; J.push_back(X[i]); }
	sort(J.begin(), J.end());
	J.erase(unique(J.begin(), J.end()), J.end());

	bitset<15009> G = ZERO; G.set(0);
	for (int i = 1; i <= N; i++) {
		if (used[i] == false) G |= (G << A[i]);
	}

	for (int i = cl; i <= cr; i++) {
		A[X[i]] = V[i];
		bitset<15009>H = G;
		for (int pos : J) H |= (H << A[pos]);
		if (H[K] == 1) ans[i] = 1;
		else ans[i] = 0;
	}
}

int main() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];
	cin >> Q;
	for (int i = 1; i <= Q; i++) cin >> X[i] >> V[i];

	for (int i = 1; i <= Q; i += BACKET) {
		int cl = i, cr = min(Q, i + BACKET - 1);
		query(cl, cr);
	}
	for (int i = 1; i <= N; i++) cout << ans[i] << endl;
	return 0;
}