把unordered_map和unordered_set改为map和set就只能得92分,会有两测试点点超时。
以下是代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 40 + 5;
ll n , a[maxm];
void dfs(int x , int mid , ll sum , ll id , map<ll , unordered_set<ll>>& c){
if(x > mid){
c[sum].insert(id);
return ;
}
dfs(x + 1 , mid , sum + a[x] , id + (1LL << x - 1) , c);
dfs(x + 1 , mid , sum - a[x] , id + (1LL << x - 1) , c);
dfs(x + 1 , mid , sum , id , c);
}
int main(){
cin >> n;
map<ll , unordered_set<ll>> c1 , c2;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
dfs(1 , n / 2 , 0 , 0 , c1);
dfs(n / 2 + 1 , n , 0 , 0 , c2);
ll ans = 0;
unordered_map<ll , bool> f;
for(auto [x , y] : c1){
if(c2.count(~x + 1)){
for(auto i : y){
for(auto j : c2[~x + 1]){
f[i + j] = true;
}
}
}
}
cout << f.size() - 1 << endl;
}