結果

問題 No.2161 Black Market
ユーザー roaris
提出日時 2022-12-12 03:39:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,387 ms / 7,000 ms
コード長 2,208 bytes
コンパイル時間 2,673 ms
コンパイル使用メモリ 223,336 KB
最終ジャッジ日時 2025-02-09 09:55:13
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
typedef long long ll;

struct BIT {
    int size;
    vector<int> node;
    
    BIT(int n) {
        size = n;
        node.resize(n+1);
    }
    
    void add(int i, int x) {
        i++;
        while (i<=size) {
            node[i] += x;
            i += i&(-i);
        }
    }
    
    int acc(int i) {
        int s = 0;
        while (i>0) {
            s += node[i];
            i -= i&(-i);
        }
        return s;
    }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    ll N, K, L, P; cin >> N >> K >> L >> P;
    ll A[N], B[N];
    rep(i, N) cin >> A[i] >> B[i];
    
    int N1 = N/2;
    vector<pair<ll, ll>> L1[N1+1];
    rep(S, 1<<N1) {
        int cnt = 0;
        ll as = 0ll;
        ll bs = 0ll;
        rep(i, N1) if ((S>>i)&1) {
            cnt++;
            as += A[i];
            bs += B[i];
        }
        L1[cnt].pb(make_pair(as, bs));
    }
    rep(i, N1+1) sort(L1[i].rbegin(), L1[i].rend());
    
    int N2 = N-N1;
    vector<pair<ll, ll>> L2[N2+1];
    rep(S, 1<<N2) {
        int cnt = 0;
        ll as = 0ll;
        ll bs = 0ll;
        rep(i, N2) if ((S>>i)&1) {
            cnt++;
            as += A[N1+i];
            bs += B[N1+i];
        }
        L2[cnt].pb(make_pair(as, bs));
    }
    rep(i, N2+1) sort(L2[i].begin(), L2[i].end());
    
    ll ans = 0ll;
    rep(c1, N1+1) rep(c2, N2+1) {
        if (c1+c2>K) continue;
        vector<ll> values;
        rep(i, L1[c1].size()) values.pb(P-L1[c1][i].second);
        rep(i, L2[c2].size()) values.pb(L2[c2][i].second);
        sort(values.begin(), values.end());
        values.erase(unique(values.begin(), values.end()), values.end());
        map<ll, int> idx;
        rep(i, values.size()) idx[values[i]] = i;
        
        BIT bit(values.size());
        int j = 0;
        rep(i, L1[c1].size()) {
            while (j<L2[c2].size() && L1[c1][i].first+L2[c2][j].first<=L) {
                bit.add(idx[L2[c2][j].second], 1);
                j++;
            }
            ans += (ll)(j-bit.acc(idx[P-L1[c1][i].second]));
        }
    }
    
    cout << ans << endl;
}
0