fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n;
  11.     ll W;
  12.     if (!(cin >> n >> W)) return 0;
  13.  
  14.     vector<pair<ll,ll>> a(n);
  15.     vector<ll> uniq;
  16.     uniq.reserve(n);
  17.     for (int i = 0; i < n; ++i) {
  18.         cin >> a[i].first >> a[i].second;
  19.         uniq.push_back(a[i].second);
  20.     }
  21.     sort(uniq.begin(), uniq.end());
  22.     uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
  23.     int m = (int)uniq.size();
  24.  
  25.     vector<vector<ll>> g(m);
  26.     for (int i = 0; i < n; ++i) {
  27.         int id = int(lower_bound(uniq.begin(), uniq.end(), a[i].second) - uniq.begin());
  28.         g[id].push_back(a[i].first);
  29.     }
  30.  
  31.     vector<ll> base;
  32.     for (int i = 0; i + 1 < m; ++i) base.push_back(uniq[i+1] / uniq[i]);
  33.  
  34.     vector<ll> cap(m, 0);
  35.     ll rem = W;
  36.     for (int i = 0; i + 1 < m; ++i) {
  37.         cap[i] = rem % base[i];
  38.         rem /= base[i];
  39.     }
  40.     cap[m-1] = rem;
  41.  
  42.     ll ans = 0;
  43.     for (int i = 0; i < m; ++i) {
  44.         auto &vec = g[i];
  45.         if (!vec.empty()) sort(vec.begin(), vec.end(), greater<ll>());
  46.         int s = (int)vec.size();
  47.         vector<ll> pref(s+1, 0);
  48.         for (int j = 0; j < s; ++j) pref[j+1] = pref[j] + vec[j];
  49.  
  50.         ll take = min<ll>(cap[i], s);
  51.         ans += pref[(int)take];
  52.  
  53.         if (i + 1 < m) {
  54.             int start = (int)take;
  55.             ll k = base[i];
  56.             int remCnt = s - start;
  57.             int groups = remCnt / (int)k;
  58.             for (int gidx = 0; gidx < groups; ++gidx) {
  59.                 int L = start + gidx * (int)k;
  60.                 int R = L + (int)k;
  61.                 g[i+1].push_back(pref[R] - pref[L]);
  62.             }
  63.         }
  64.     }
  65.  
  66.     cout << ans << '\n';
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
20 10000
222512691052 4096
5620511391 128
5142775228 64
197742659477 4096
525759354129 8192
19003783939 512
174609615733 4096
457491007 8
18306808974 256
990496677 16
4230766729 128
11201398381 256
73572867768 1024
8799846673 128
1968851699 32
6401370480 128
1010805215 16
64930386449 1024
54501354 1
288867560088 4096
stdout 
645052451620
https://ideone.com/18g0dc
language:
C++14 (gcc 8.3)
created:
14 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!