提出 #75559662

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int M = (int)4e6 + 10;

typedef bitset<M> bs;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int>a(n+1);
    vector<int>f(M+1);
    for(int i = 1; i<=n; i++){
        cin >> a[i];
        f[a[i]] += 2;
    }
    bs b;
    b[0] = 1;
    for(int i = 1; i<=M; i++){
        while(f[i] >= 3){
            f[i] -= 2;
            f[2*i]++;
        }
        for(int j = 0; j<f[i]; j++){
            b = b | (b << i);
        }
    }
    cout << (b.count()+1)/2 << '\n';
    return 0;
}

提出情報

ジャッジ結果