結果

問題 No.2161 Black Market
ユーザー suisen
提出日時 2022-12-24 03:44:57
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 7,000 ms
コード長 2,833 bytes
コンパイル時間 4,955 ms
コンパイル使用メモリ 138,824 KB
最終ジャッジ日時 2025-02-09 19:55:05
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <atcoder/fenwicktree>
std::vector<std::vector<std::pair<int64_t, int64_t>>> enumerate_all(
const size_t N,
const size_t K,
const std::vector<int64_t> w,
const std::vector<int64_t> v
) {
std::vector<std::vector<std::pair<int64_t, int64_t>>> res(K + 1);
res[0].emplace_back(0, 0);
for (size_t i = 0; i < N; ++i) {
std::vector<std::size_t> mid(K + 1);
for (size_t j = 1; j <= K; ++j) {
mid[j] = res[j].size();
}
for (size_t j = K; j --> 0;) {
for (const auto& [wsum, vsum] : res[j]) {
res[j + 1].emplace_back(wsum + w[i], vsum + v[i]);
}
}
for (size_t j = 1; j <= K; ++j) {
std::inplace_merge(res[j].begin(), res[j].begin() + mid[j], res[j].end());
}
}
return res;
}
int64_t solve(
const size_t N,
const size_t K,
const int64_t W,
const int64_t V,
const std::vector<int64_t> w,
const std::vector<int64_t> v
) {
const size_t H = N / 2;
auto L = enumerate_all(
H, K,
std::vector<int64_t>(w.begin(), w.begin() + H),
std::vector<int64_t>(v.begin(), v.begin() + H)
);
auto R = enumerate_all(
N - H, K,
std::vector<int64_t>(w.begin() + H, w.end()),
std::vector<int64_t>(v.begin() + H, v.end())
);
int64_t ans = 0;
for (size_t j = 0; j <= K; ++j) {
std::vector<int64_t> comp_v;
for (const auto &e : R[j]) {
comp_v.emplace_back(e.second);
}
std::sort(comp_v.begin(), comp_v.end());
comp_v.erase(std::unique(comp_v.begin(), comp_v.end()), comp_v.end());
for (auto &e : R[j]) {
e.second = std::lower_bound(comp_v.begin(), comp_v.end(), e.second) - comp_v.begin();
}
const size_t m = comp_v.size();
for (size_t i = 0; i + j <= K; ++i) {
atcoder::fenwick_tree<uint32_t> ft(m);
auto itR = R[j].begin();
for (auto itL = L[i].rbegin(); itL != L[i].rend(); ++itL) {
auto [wsum, vsum] = *itL;
int64_t maxw = W - wsum;
for (; itR != R[j].end() and itR->first <= maxw; ++itR) {
ft.add(itR->second, 1);
}
int64_t maxv = V - vsum;
std::size_t l = std::lower_bound(comp_v.begin(), comp_v.end(), maxv) - comp_v.begin();
ans += ft.sum(l, m);
}
}
}
return ans;
}
int main() {
size_t N, K;
int64_t W, V;
std::cin >> N >> K >> W >> V;
std::vector<int64_t> w(N), v(N);
for (size_t i = 0; i < N; ++i) {
std::cin >> w[i] >> v[i];
}
std::cout << solve(N, K, W, V, w, v) << std::endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0