fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using i64  = long long;
  4. using i128 = __int128_t;          // prevents overflow when we divide M
  5.  
  6. const i64 NEG = -(1LL<<62);       // -INF
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.  
  12.     int N;        i64 M;
  13.     if(!(cin >> N >> M)) return 0;
  14.  
  15.     vector<i64> v(N), m(N);
  16.     for (int i = 0; i < N; ++i) cin >> v[i] >> m[i];
  17.  
  18.     /* ---- 1. group by identical mass ----------------------------------- */
  19.     vector<i64> masses = m;
  20.     sort(masses.begin(), masses.end());
  21.     masses.erase(unique(masses.begin(), masses.end()), masses.end());
  22.     int K = (int)masses.size();
  23.     vector<vector<i64>> grp(K);
  24.  
  25.     unordered_map<i64,int> idx;
  26.     for (int i=0;i<K;++i) idx[masses[i]]=i;
  27.  
  28.     for (int i = 0; i < N; ++i)
  29.         grp[idx[m[i]]].push_back(v[i]);
  30.  
  31.     for (auto &g: grp) sort(g.rbegin(), g.rend());   // big values first
  32.  
  33.     /* ---- 2. pre-compute ratios r[i] ----------------------------------- */
  34.     vector<i64> r(K-1);
  35.     for (int i=0;i+1<K;++i) r[i] = masses[i+1] / masses[i];
  36.  
  37.     /* ---- 3. DP --------------------------------------------------------- */
  38.     i64 C = M / masses[0];                // capacity in w0-units
  39.     vector<i64> dp(C+1, NEG);
  40.     dp[0] = 0;
  41.  
  42.     i64 mult = 1;                         // w_i / w0  (in w0-units)
  43.  
  44.     for (int i = 0; i < K; ++i) {
  45.         const auto &g = grp[i];
  46.         int cnt = (int)g.size();
  47.         if (cnt == 0) {                   // nothing to do
  48.             if (i+1 < K) { mult *= r[i];  // scale for next tier
  49.                 /* compress: keep every mult'th entry */
  50.                 vector<i64> nxt(r[i], NEG);
  51.                 for (i64 w = 0; w <= C; ++w)
  52.                     if (dp[w] != NEG)
  53.                         nxt[w % r[i]] = max(nxt[w % r[i]], dp[w]);
  54.                 dp.swap(nxt);
  55.                 C = r[i]-1;
  56.             }
  57.             continue;
  58.         }
  59.  
  60.         /* bounded-knapsack with weight = mult, values = g[0..cnt-1] */
  61.         i64 W = mult;                     // current item weight
  62.  
  63.         /* deque optimisation, residue classes modulo W */
  64.         for (i64 rem = 0; rem < W && rem <= C; ++rem) {
  65.             deque<pair<i64,i64>> dq;      // (index, value)
  66.             for (i64 t = 0, idxw = rem; idxw <= C; ++t, idxw += W) {
  67.                 i64 base = dp[idxw];
  68.                 if (base != NEG) {        // push candidate
  69.                     base -= t < (i64)cnt ? 0 : (i64)g.back()+1; // keep monotone
  70.                     while (!dq.empty() && dq.back().second <= base)
  71.                         dq.pop_back();
  72.                     dq.emplace_back(t, base);
  73.                 }
  74.  
  75.                 while (!dq.empty() && dq.front().first + cnt < t)
  76.                     dq.pop_front();
  77.  
  78.                 if (!dq.empty() && t < (i64)cnt) {
  79.                     i64 gain = g[t];      // t-th best value
  80.                     dp[idxw] = max(dp[idxw], dq.front().second + gain);
  81.                 }
  82.             }
  83.         }
  84.  
  85.         /* finished weight w_i, prepare for next tier */
  86.         if (i + 1 < K) {
  87.             mult *= r[i];
  88.             vector<i64> nxt(r[i], NEG);
  89.             for (i64 w = 0; w <= C; ++w)
  90.                 if (dp[w] != NEG)
  91.                     nxt[w % r[i]] = max(nxt[w % r[i]], dp[w]);
  92.             dp.swap(nxt);
  93.             C = r[i]-1;
  94.         }
  95.     }
  96.  
  97.     cout << *max_element(dp.begin(), dp.end()) << '\n';
  98.     return 0;
  99. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RKZcvL
language:
C++ (gcc 8.3)
created:
3 days 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!