fork 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_pos(long long a, long long r){
  8.     // ceil(a/r) but clamp to >=0
  9.     if (a <= 0) return 0;
  10.     return (a + r - 1) / r;
  11. }
  12.  
  13. int main() {
  14.     ios::sync_with_stdio(false);
  15.     cin.tie(nullptr);
  16.  
  17.     int N; long long W;
  18.     if (!(cin >> N >> W)) return 0;
  19.  
  20.     // Gom theo weight
  21.     unordered_map<long long, vector<long long>> mp;
  22.     mp.reserve(N * 2);
  23.     for (int i = 0; i < N; ++i) {
  24.         long long v, w; cin >> v >> w;
  25.         mp[w].push_back(v);
  26.     }
  27.  
  28.     // Danh sách trọng lượng phân biệt
  29.     vector<long long> b;
  30.     b.reserve(mp.size());
  31.     for (auto &kv : mp) b.push_back(kv.first);
  32.     sort(b.begin(), b.end());
  33.     int m = (int)b.size();
  34.  
  35.     // Giá trị theo nhóm (giảm dần) và prefix
  36.     vector<vector<long long>> vals(m);
  37.     vector<int> cnt(m);
  38.     for (int i = 0; i < m; ++i) {
  39.         auto &v = mp[b[i]];
  40.         sort(v.begin(), v.end(), greater<long long>());
  41.         vals[i] = move(v);
  42.         cnt[i] = (int)vals[i].size();
  43.     }
  44.  
  45.     // L_k, r_k, Delta_k
  46.     vector<long long> L(m);
  47.     for (int i = 0; i < m; ++i) L[i] = W / b[i];
  48.  
  49.     vector<long long> r(m-1), Delta(m-1);
  50.     for (int i = 0; i + 1 < m; ++i) {
  51.         r[i] = b[i+1] / b[i];                      // bảo đảm chia hết theo giả thiết đề
  52.         Delta[i] = L[i] - r[i]*L[i+1];             // 0 <= Delta < r
  53.     }
  54.  
  55.     // Tính need ngược chiều
  56.     vector<long long> need(m, 0);
  57.     need[0] = 0;
  58.     for (int k = 0; k + 1 < m; ++k) {
  59.         long long Lk = L[k], rk = r[k], Dk = Delta[k];
  60.         long long M = min(Lk, (long long)cnt[k] + need[k]);
  61.         long long nxt = ceil_div_pos(M - Dk, rk);
  62.         if (nxt > L[k+1]) nxt = L[k+1];
  63.         need[k+1] = nxt;
  64.     }
  65.  
  66.     auto make_pref = [&](int idx, long long K)->vector<long long> {
  67.         K = min<long long>(K, cnt[idx]);
  68.         vector<long long> pref(K + 1, 0);
  69.         long long s = 0;
  70.         for (long long i = 0; i < K; ++i) {
  71.             s += vals[idx][(int)i];
  72.             pref[(size_t)i + 1] = s;
  73.         }
  74.         return pref; // pref[t] = tổng t món đầu
  75.     };
  76.  
  77.     // Base: lớp nặng nhất
  78.     vector<long long> H; // H[u] = F_{k}(L_k - u) của lớp hiện tại
  79.     {
  80.         int k = m - 1;
  81.         auto pref = make_pref(k, L[k]);
  82.         long long needk = need[k];
  83.         H.assign((size_t)needk + 1, NEG);
  84.         for (long long u = 0; u <= needk; ++u) {
  85.             long long cap = L[k] - u;
  86.             if (cap < 0) { H[(size_t)u] = NEG; continue; }
  87.             long long take = min<long long>(cnt[k], cap);
  88.             H[(size_t)u] = pref[(size_t)take];
  89.         }
  90.     }
  91.  
  92.     // Xuống các lớp nhẹ hơn
  93.     for (int k = m - 2; k >= 0; --k) {
  94.         long long Lk = L[k], rk = r[k], Dk = Delta[k];
  95.         long long needk = need[k], needNext = need[k+1];
  96.  
  97.         long long Kcap = min<long long>(cnt[k], Lk);
  98.         auto pref = make_pref(k, Kcap);
  99.  
  100.         vector<long long> G((size_t)needk + 1, NEG);
  101.  
  102.         long long maxResidue = min<long long>(rk - 1, Kcap);
  103.         for (long long j = 0; j <= maxResidue; ++j) {
  104.             // A[q] = pref[j + q*rk], q=0..len_j-1
  105.             long long len_j = (Kcap >= j) ? ((Kcap - j) / rk + 1) : 0;
  106.             if (len_j == 0) continue;
  107.  
  108.             // Duyệt từng s (base) và xử lý block u tương ứng
  109.             for (long long s = 0; s <= needNext; ++s) {
  110.                 // q tối đa vì cần H[s+q] tồn tại
  111.                 long long xmax_s = min<long long>(len_j - 1, needNext - s);
  112.                 if (xmax_s < 0) continue;
  113.  
  114.                 // prefix max PM[x] = max_{q<=x} ( pref[j + q*r] + H[s+q] )
  115.                 vector<long long> PM((size_t)xmax_s + 1);
  116.                 PM[0] = pref[(size_t)j] + H[(size_t)(s + 0)];
  117.                 for (long long x = 1; x <= xmax_s; ++x) {
  118.                     long long cand = pref[(size_t)(j + x*rk)] + H[(size_t)(s + x)];
  119.                     PM[(size_t)x] = max(PM[(size_t)(x - 1)], cand);
  120.                 }
  121.  
  122.                 // Block u mà base(u)=s:
  123.                 long long left_u, right_u;
  124.                 if (s == 0) {
  125.                     right_u = Dk - j;
  126.                     left_u  = 0;
  127.                 } else {
  128.                     left_u  = rk*(s - 1) - (j - Dk) + 1;
  129.                     right_u = rk*s       - (j - Dk);
  130.                 }
  131.                 if (right_u < 0 || left_u > needk) continue;
  132.                 left_u  = max<long long>(left_u, 0);
  133.                 right_u = min<long long>(right_u, needk);
  134.  
  135.                 for (long long u = left_u; u <= right_u; ++u) {
  136.                     long long limitA = min<long long>(Kcap, Lk - u);
  137.                     if (limitA < j) continue;
  138.                     long long Xu = (limitA - j) / rk;        // q upper bởi sức chứa
  139.                     long long xu = min<long long>(Xu, xmax_s);
  140.                     G[(size_t)u] = max(G[(size_t)u], PM[(size_t)xu]);
  141.                 }
  142.             }
  143.         }
  144.  
  145.         H.swap(G);
  146.     }
  147.  
  148.     cout << H[0] << '\n';
  149.     return 0;
  150. }
  151.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 10
1 1
6 2
20 6
8 2
5 2
10 1
stdout
copy 
39
https://ideone.com/VhNEl4
language:
C++14 (clang 8.0)
created:
8 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!