結果

問題 No.2161 Black Market
ユーザー roarisroaris
提出日時 2022-12-12 03:39:20
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,124 ms / 7,000 ms
コード長 2,208 bytes
コンパイル時間 2,819 ms
コンパイル使用メモリ 230,180 KB
実行使用メモリ 11,568 KB
最終ジャッジ日時 2023-08-06 00:59:26
合計ジャッジ時間 10,740 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,508 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,384 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 119 ms
8,788 KB
testcase_21 AC 119 ms
8,996 KB
testcase_22 AC 132 ms
8,768 KB
testcase_23 AC 159 ms
8,748 KB
testcase_24 AC 2,124 ms
11,568 KB
testcase_25 AC 326 ms
9,484 KB
testcase_26 AC 1,760 ms
11,312 KB
testcase_27 AC 45 ms
8,476 KB
testcase_28 AC 51 ms
8,428 KB
testcase_29 AC 20 ms
4,792 KB
testcase_30 AC 35 ms
4,380 KB
testcase_31 AC 832 ms
9,460 KB
testcase_32 AC 42 ms
8,476 KB
testcase_33 AC 91 ms
4,376 KB
testcase_34 AC 11 ms
4,384 KB
testcase_35 AC 11 ms
4,488 KB
testcase_36 AC 64 ms
4,380 KB
testcase_37 AC 33 ms
4,380 KB
testcase_38 AC 349 ms
6,372 KB
testcase_39 AC 14 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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