この問題は私を狂わせています。上のコードは私のコンピューターでは約0.3秒で実行され、下のコードは約2.7秒で実行されます。ただし、2番目のコードを最初のコードとできるだけ似るように調整しようとしましたが、常に遅くなっているようです。最初のコードが2番目のコードよりもはるかに高速に実行される理由を誰かに教えてもらえますか？
より高速なコード
#include <cstdio>
#include <set>
#define ls(x) (x & (-x))
using namespace std;
int tc, n;
set<long long> s;
long long p, a[35];
int main () {
freopen("mini3b.in","r",stdin);
scanf("%d", &tc);
while (tc--) {
s.clear();
scanf("%lld%d", &p, &n);
for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
int h = n/2;
for (int i = 0; i < (1<<h); ++i) {
long long sum = 0;
for (int j = 0; j < h; ++j) if (i&(1<<j)) sum += a[j];
s.insert(sum);
}
bool found = false;
for (int i = 0; (i < (1<<(n-h))) && !found; ++i) {
long long sum = 0;
for (int j = 0; j < n-h; ++j) if (i&(1<<j)) sum += a[h+j];
if (s.find(p-sum) != s.end()) found = true;
}
printf(found? "YES\n":"NO\n");
}
}
遅いコード
#include <cstdio>
#include <set>
using namespace std;
long long n, bars[35];
int t, p;
set<long long> s;
int main(){
freopen("mini3b.in","r", stdin);
scanf("%d", &t);
while (t--){
s.clear();
scanf("%lld%d", &n, &p);
for (int i=0;i<p;++i) scanf("%lld", &bars[i]);
int limit=p/2;
for (int i=0;i<(1<<limit);++i){
long long sum=0;
for (int j=0;j<limit;++j) if (i&(1<<j)) sum+=bars[j];
s.insert(sum);
}
bool found=false;
for (int i=0;i<(1<<(n-limit))&&!found;++i){
long long sum=0;
for (int j=0;j<p-limit;++j) if (i&(1<<j)) sum+=bars[limit+j];
if (s.find(n-sum) != s.end())
found=true;
}
printf(found?"YES\n":"NO\n");
}
}