結果
問題 | No.2161 Black Market |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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;}