fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using int64 = long long;
  5. const long long NEG = (long long)-4e18;
  6.  
  7. static inline long long ceil_div_nonneg(long long x, long long r) {
  8.     if (x <= 0) return 0LL;              // clamp lên 0 (không mượn thêm sức chứa ở lớp trên)
  9.     return (x + r - 1) / r;              // x>0
  10. }
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.  
  16.     int N;
  17.     long long W;
  18.     if (!(cin >> N >> W)) return 0;
  19.  
  20.     // Gom theo weight
  21.     unordered_map<long long, vector<long long>> bucket;
  22.     bucket.reserve(N*2);
  23.     vector<pair<long long,long long>> items;
  24.     items.reserve(N);
  25.  
  26.     for (int i = 0; i < N; ++i) {
  27.         long long v, w; 
  28.         cin >> v >> w;
  29.         bucket[w].push_back(v);
  30.     }
  31.  
  32.     // Lấy danh sách weight phân biệt và sort tăng
  33.     vector<long long> b;
  34.     b.reserve(bucket.size());
  35.     for (auto &kv : bucket) {
  36.         b.push_back(kv.first);
  37.     }
  38.     sort(b.begin(), b.end()); // b[0] nhỏ nhất
  39.  
  40.     int m = (int)b.size();
  41.     vector<vector<long long>> vals(m);
  42.     vector<int> cnt(m);
  43.     for (int i = 0; i < m; ++i) {
  44.         auto &vec = bucket[b[i]];
  45.         sort(vec.begin(), vec.end(), greater<long long>());
  46.         vals[i] = move(vec);
  47.         cnt[i] = (int)vals[i].size();
  48.     }
  49.  
  50.     // Tính L_k = floor(W / b_k), r_k = b_{k+1}/b_k, Delta_k = L_k - r_k * L_{k+1}
  51.     vector<long long> L(m);
  52.     for (int i = 0; i < m; ++i) L[i] = W / b[i];
  53.  
  54.     vector<long long> r(m-1), Delta(m-1);
  55.     for (int i = 0; i+1 < m; ++i) {
  56.         // Với đề bài, b[i+1] % b[i] == 0 luôn đúng (do dãy chia hết)
  57.         r[i] = b[i+1] / b[i];
  58.         Delta[i] = L[i] - r[i]*L[i+1];
  59.         // assert(0 <= Delta[i] && Delta[i] < r[i]);
  60.     }
  61.  
  62.     // Tính "need" ngược chiều: need[k] = cần F_k(L_k - t) với t ∈ [0..need[k]]
  63.     // Ban đầu chỉ cần F_0(L_0) -> need[0] = 0
  64.     vector<long long> need(m, 0);
  65.     need[0] = 0;
  66.     for (int k = 0; k+1 < m; ++k) {
  67.         long long Lk = L[k];
  68.         long long rk = r[k];
  69.         long long Dk = Delta[k];
  70.         long long needk = need[k];
  71.         long long Ck = cnt[k];
  72.  
  73.         // M = max_{t∈[0..needk]} ( t + min(Ck, Lk - t) )  = min(Lk, needk + Ck)
  74.         long long M = min(Lk, needk + Ck);
  75.  
  76.         long long x = M - Dk;
  77.         long long nextNeed = (x <= 0) ? 0 : ( (x + rk - 1) / rk );
  78.         if (nextNeed > L[k+1]) nextNeed = L[k+1];
  79.         need[k+1] = nextNeed;
  80.     }
  81.  
  82.     // Hàm xây prefix sum top-K của 1 nhóm (chỉ cần đến min(cnt, Klimit))
  83.     auto build_prefix = [&](int idx, long long Klimit)->vector<long long> {
  84.         long long K = min<long long>(cnt[idx], Klimit);
  85.         vector<long long> pref;
  86.         pref.reserve((size_t)K + 1);
  87.         pref.push_back(0);
  88.         long long acc = 0;
  89.         for (long long i = 0; i < K; ++i) {
  90.             acc += vals[idx][(int)i];
  91.             pref.push_back(acc);
  92.         }
  93.         return pref; // pref[t] = tổng t món tốt nhất
  94.     };
  95.  
  96.     // Base: lớp nặng nhất m-1
  97.     vector<long long> h; // h[u] = F_{k}(L_k - u) tại lớp hiện tại (khởi đầu: k = m-1)
  98.     {
  99.         int k = m-1;
  100.         long long needk = need[k];
  101.         vector<long long> pref_last = build_prefix(k, L[k]); // pick ≤ min(cnt, L[k])
  102.         h.assign((size_t)needk + 1, NEG);
  103.         for (long long u = 0; u <= needk; ++u) {
  104.             long long cap = L[k] - u;               // còn lại bao nhiêu slot của b_k
  105.             if (cap < 0) { h[(size_t)u] = NEG; continue; }
  106.             long long take = min<long long>(cnt[k], cap);
  107.             h[(size_t)u] = pref_last[(size_t)take];
  108.         }
  109.     }
  110.  
  111.     // Chuyển từ lớp k+1 -> k, lần lượt k = m-2..0
  112.     for (int k = m-2; k >= 0; --k) {
  113.         long long Lk = L[k];
  114.         long long rk = r[k];
  115.         long long Dk = Delta[k];
  116.         long long needk = need[k];
  117.         long long needNext = need[k+1];
  118.  
  119.         // prefix của nhóm k (chỉ cần đến K = min(cnt, Lk))
  120.         long long Kcap = min<long long>(cnt[k], Lk);
  121.         vector<long long> pref_k = build_prefix(k, Kcap);
  122.  
  123.         // Ghi chú: với j > Kcap thì không có a ≡ j (mod rk) khả dụng.
  124.         long long maxResidue = min<long long>(rk-1, Kcap);
  125.  
  126.         // Kết quả g[t] = F_k(Lk - t), t=0..needk
  127.         vector<long long> g((size_t)needk + 1, NEG);
  128.  
  129.         // Với mỗi residue j, ta duyệt tất cả s = ceil((t + j - Dk)/rk) theo block t
  130.         for (long long j = 0; j <= maxResidue; ++j) {
  131.             // A_j[x] = pref_k[j + x*rk], x = 0..len_j-1
  132.             long long len_j = (Kcap >= j) ? ((Kcap - j) / rk + 1) : 0;
  133.             if (len_j == 0) continue;
  134.  
  135.             // Tiền xử lý theo từng s: PM_s[x] = max_{q<=x} ( A_j[q] + h[s+q] )
  136.             // Nhưng chỉ cần đến x ≤ min(len_j-1, needNext - s)
  137.             // Để tiết kiệm bộ nhớ, làm s lần lượt, build 1 mảng PM rồi đổ vào các t trong block của (j,s)
  138.             for (long long s = 0; s <= needNext; ++s) {
  139.                 long long xmax_s = min<long long>(len_j - 1, needNext - s);
  140.                 if (xmax_s < 0) continue;
  141.  
  142.                 vector<long long> PM;
  143.                 PM.resize((size_t)xmax_s + 1);
  144.                 // PM[0]
  145.                 PM[0] = pref_k[(size_t)(j)] + h[(size_t)(s + 0)];
  146.                 for (long long x = 1; x <= xmax_s; ++x) {
  147.                     long long val = pref_k[(size_t)(j + x * rk)] + h[(size_t)(s + x)];
  148.                     PM[(size_t)x] = max(PM[(size_t)(x - 1)], val);
  149.                 }
  150.  
  151.                 // t thuộc block: base_j(t) = s  <=>  rk*s - (j - Dk) ≤ t ≤ rk*s + rk - 1 - (j - Dk)
  152.                 long long left_t  = rk * s - (j - Dk);
  153.                 long long right_t = rk * s + rk - 1 - (j - Dk);
  154.                 if (right_t < 0 || left_t > needk) continue;
  155.                 left_t  = max<long long>(left_t, 0);
  156.                 right_t = min<long long>(right_t, needk);
  157.  
  158.                 for (long long t = left_t; t <= right_t; ++t) {
  159.                     // Giới hạn a ≤ min(Kcap, Lk - t) và a ≡ j (mod rk)
  160.                     long long limitA = min<long long>(Kcap, Lk - t);
  161.                     if (limitA < j) continue;
  162.                     long long Xt = (limitA - j) / rk;
  163.                     long long xu = min<long long>(Xt, xmax_s);
  164.                     // PM[xu] là max của pref[j + q*r] + h[s+q] với q ≤ xu
  165.                     g[(size_t)t] = max(g[(size_t)t], PM[(size_t)xu]);
  166.                 }
  167.             }
  168.         }
  169.  
  170.         h.swap(g); // h trở thành F_k(Lk - t) cho t ∈ [0..needk]
  171.     }
  172.  
  173.     cout << h[0] << '\n';
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6 10
1 1
6 2
20 6
8 2
5 2
10 1
stdout
copy 
45
https://ideone.com/BBkoLj
language:
C++14 (clang 8.0)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!