C - A+B+C Editorial by MMNMM
空間のオーバーヘッドを無視した場合、連続する \(3\times10 ^ 8+1\operatorname{bit}\) を直接管理できればこの問題を解くことができます(\(3\times10 ^ 8+1\operatorname{bit}\) は約 \(37.5\operatorname{MB}\) で、メモリ制限に対して余裕があります)。
C++ などでは std::bitset
などを使うことで余計な空間をほとんど使うことなく連続するビットを扱うことができます。
時間計算量は \(O(NML+Q)\) となります。
#include <iostream>
#include <vector>
#include <bitset>
int main() {
using namespace std;
unsigned N, M, L;
cin >> N;
vector<unsigned> A(N);
for (auto &&a : A)
cin >> a;
cin >> M;
vector<unsigned> B(M);
for (auto &&b : B)
cin >> b;
cin >> L;
vector<unsigned> C(L);
for (auto &&c : C)
cin >> c;
// 連続する 3e8 + 1 bit を用意して
// A[i] + B[j] + C[k] として出現する値かどうかを管理
bitset<300000001> possible;
for (const auto a : A)
for (const auto b : B)
for (const auto c : C)
possible[a + b + c] = true;
unsigned Q;
cin >> Q;
for (unsigned i = 0, x; i < Q; ++i) {
cin >> x;
cout << (possible[x] ? "Yes" : "No") << endl;
}
return 0;
}
posted:
last update: