fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(v) begin(v), end(v)
  4. #define fi first
  5. #define se second
  6. #define dbg(x) "[" #x " = " << x << "]"
  7.  
  8. #define left __left
  9. #define right __right
  10.  
  11. #define MASK(i) (1LL << (i))
  12. #define BIT(x, i) (((x) >> (i)) & 1)
  13.  
  14. using namespace std;
  15.  
  16. bool M1;
  17. const int infINT = 1e9 + 123;
  18. const long long inf = 1e18 + 123;
  19.  
  20. typedef pair<int, int > ii;
  21. typedef pair<long long, int > lli;
  22.  
  23. const int MAXN = MASK(19) + 10;
  24.  
  25. int numVal, val[MAXN];
  26. long long numLim, cost[MAXN];
  27. pair<long long, int > tot[MAXN];
  28. bool choose[MAXN];
  29.  
  30. void input(){
  31.     cin >> numVal >> numLim;
  32.     for(int i = 1; i <= numVal; i++) cin >> val[i];
  33.     for(int i = 1; i <= numVal; i++) cin >> cost[i];
  34. }
  35.  
  36. bool check(const int &m){
  37.     for(int i = 1; i <= numVal; i++){
  38.         if (max(0, (m - val[i])) <= numLim / cost[i])
  39.             tot[i].fi = 1LL * max(0, (m - val[i])) * cost[i];
  40.         else
  41.             tot[i].fi = numLim + 1;
  42.         tot[i].se = i;
  43.     }
  44.  
  45.     if (m < numVal) nth_element(tot + 1, tot + 1 + m, tot + 1 + numVal);
  46.  
  47.     long long sum = 0;
  48.     for(int i = 1; i <= m; i++){
  49.         if (sum > numLim - tot[i].fi) return 0;
  50.         sum += tot[i].fi;
  51.     }
  52.  
  53.     for(int i = 1; i <= numVal; i++){
  54.         choose[tot[i].se] = (i <= m);
  55.     }
  56.  
  57.     return 1;
  58. }
  59.  
  60. void solve(){
  61.     int l = 1, r = numVal, res = 0, m;
  62.     while(l <= r){
  63.         m = (l + r) >> 1;
  64.         if (check(m)) res = m, l = m + 1;
  65.         else r = m - 1;
  66.     }
  67.     cout << res << '\n';
  68.     for(int i = 1; i <= numVal; i++){
  69.         cout << (choose[i] ? max(res, val[i]): val[i]) - val[i] << ' ';
  70.     }
  71. }
  72.  
  73. bool M2;
  74. signed main(){
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.     #define task "hindex"
  77.     if (fopen(task".inp", "r")){
  78.         freopen(task".inp", "r", stdin);
  79.         freopen(task".out", "w", stdout);
  80.     }
  81.     input();
  82.     solve();
  83.     cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
  84.     cerr << (&M2 - &M1) / 1048576 << " mb\n";
  85. }
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
0.004157.s
-14 mb
https://ideone.com/er2yWD
language:
C++14 (gcc 8.3)
created:
9 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!