結果

問題 No.2161 Black Market
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2022-11-23 15:00:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,085 ms / 7,000 ms
コード長 4,290 bytes
コンパイル時間 1,403 ms
コンパイル使用メモリ 110,256 KB
実行使用メモリ 23,820 KB
最終ジャッジ日時 2024-10-14 18:40:20
合計ジャッジ時間 7,724 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 4 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 3 ms
5,248 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 4 ms
5,248 KB
testcase_18 AC 3 ms
5,248 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 274 ms
13,220 KB
testcase_21 AC 276 ms
13,224 KB
testcase_22 AC 272 ms
13,224 KB
testcase_23 AC 279 ms
13,220 KB
testcase_24 AC 1,085 ms
23,820 KB
testcase_25 AC 272 ms
23,820 KB
testcase_26 AC 1,028 ms
23,692 KB
testcase_27 AC 132 ms
23,820 KB
testcase_28 AC 132 ms
23,692 KB
testcase_29 AC 33 ms
9,852 KB
testcase_30 AC 21 ms
6,272 KB
testcase_31 AC 593 ms
18,804 KB
testcase_32 AC 133 ms
23,692 KB
testcase_33 AC 49 ms
7,040 KB
testcase_34 AC 24 ms
8,704 KB
testcase_35 AC 29 ms
9,980 KB
testcase_36 AC 42 ms
7,552 KB
testcase_37 AC 25 ms
6,144 KB
testcase_38 AC 271 ms
12,076 KB
testcase_39 AC 14 ms
6,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
typedef long long ll;
using namespace std;
using pll = pair<ll,ll>;

struct BIT{
    //Binary Indexed Tree.
    ll N;
    vector<ll> vec;
    BIT(ll N_): N(N_), vec(N + 1){
        for (ll i = 0; i < N + 1; i++){
            vec[i] = 0;
        }
    }
    
    void add(ll p, ll x){
        if (p == 0){
            return;
        }
        for (ll i = p; i <= N; i += (i & -i)){
            vec[i] += x;
        }
    }

    ll sum(ll p){
        if (p == 0){
            return 0;
        }
        ll sum = 0;
        for (ll i = p; i > 0; i -= (i & -i)){
            sum += vec[i];
        }
        return sum;
    }
};

vector<vector<pll>> MakeVec(vector<pll> &vec){
    ll len = vec.size();
    vector<vector<pll>> ret(len + 1, vector<pll>(0));
    for (ll i = 0; i < (1 << len); i++){
        ll popcnt = 0;
        ll b = 0;
        ll a = 0;
        for (ll j = 0; j < len; j++){
            if ((i >> j) & 1){
                popcnt++;
                b += vec[j].first;
                a += vec[j].second;
            }
        }
        ret[popcnt].push_back(pll(b, a));
    }
    for (ll i = 0; i <= len; i++){
        sort(ret[i].begin(), ret[i].end());
    }
    return ret;
}

vector<ll> MakeUniqueA(vector<vector<pll>> &vec){
    vector<ll> ret(0);
    for (ll i = 0; i < vec.size(); i++){
        for (ll j = 0; j < vec[i].size(); j++){
            ret.push_back(vec[i][j].second);
        }
    }
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
}

int main(){
    ll N, K, L, P;
    cin >> N >> K >> L >> P;
    vector<ll> A(N);
    vector<ll> B(N);
    for (ll i = 0; i < N; i++){
        cin >> A[i] >> B[i];
    }
    vector<pll> p(N);
    for (ll i = 0; i < N; i++){
        p[i].first = A[i];
        p[i].second = B[i];
    }
    sort(p.begin(), p.end());
    for (ll i = 0; i < N; i++){
        A[i] = p[i].first;
        B[i] = p[i].second;
    }

    vector<pll> former(0);
    vector<pll> latter(0);
    for (ll i = 0; i < N / 2; i++) former.push_back(pll(B[i], A[i]));
    for (ll i = N / 2; i < N; i++) latter.push_back(pll(B[i], A[i]));

    vector<vector<pll>> former_vec = MakeVec(former);
    vector<vector<pll>> latter_vec = MakeVec(latter);

    vector<ll> former_a = MakeUniqueA(former_vec);
    vector<ll> latter_a = MakeUniqueA(latter_vec);

    //formerのほうを全探索する方針を取ることにする
    //そうすると，BITにはlatter_bの値（を座標圧縮した値）を追加することにしよう．

    unordered_map<ll, ll> mp_latter;
    for (ll i = 0; i < latter_a.size(); i++){
        mp_latter[latter_a[i]] = i + 1;
    }
    unordered_map<ll, ll> mp_former;
    for (ll i = 0; i < former_a.size(); i++){
        mp_former[former_a[i]] = i + 1;
    }

    vector<ll> idx(former_a.size());
    for (ll i = 0; i < former_a.size(); i++){
        if (former_a[i] + latter_a[latter_a.size() - 1] <= L){
            idx[i] = latter_a.size();
        }
        else if (former_a[i] + latter_a[0] > L){
            idx[i] = 0;
        }
        else{
            auto itr = upper_bound(latter_a.begin(), latter_a.end(), L - former_a[i]);
            idx[i] = itr - latter_a.begin();
        }
    }

    BIT bit((1 << 18) + 1);
    ll ans = 0;

    for (ll i = 0; i < former_vec.size(); i++){
        for (ll j = 0; j < latter_vec.size(); j++){
            if (i + j > K){
                continue;
            }
            ll now = latter_vec[j].size() - 1;
            for (ll k = 0; k < former_vec[i].size(); k++){
                while(now >= 0){
                    if (former_vec[i][k].first + latter_vec[j][now].first >= P){
                        bit.add(mp_latter[latter_vec[j][now].second], 1);
                        now--;
                    }
                    else{
                        break;
                    }
                }
                ll sm = bit.sum(idx[mp_former[former_vec[i][k].second] - 1]);
                ans += sm;
            }
            for (ll k = now + 1; k < latter_vec[j].size(); k++){
                bit.add(mp_latter[latter_vec[j][k].second], -1);
            }
        }
    }
    cout << ans << endl;

    return 0;
}
0