fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. int n;
  6. ll S;
  7. vector<ll> a;
  8.  
  9. pair<int, ll> maxSouvenirs() {
  10.     int l = 0, r = n, best_k = 0;
  11.     ll best_cost = 0;
  12.  
  13.     while (l <= r) {
  14.         int mid = (l + r) / 2;
  15.         vector<ll> cost(n);
  16.         for (int i = 0; i < n; i++) {
  17.             cost[i] = a[i] + 1LL * (i + 1) * mid;
  18.         }
  19.         sort(cost.begin(), cost.end());
  20.  
  21.         ll total = 0;
  22.         for (int i = 0; i < mid; i++) total += cost[i];
  23.  
  24.         if (total <= S) {
  25.             best_k = mid;
  26.             best_cost = total;
  27.             l = mid + 1;
  28.         } else {
  29.             r = mid - 1;
  30.         }
  31.     }
  32.  
  33.     return {best_k, best_cost};
  34. }
  35.  
  36. int main() {
  37.     ios::sync_with_stdio(false);
  38.     cin.tie(nullptr);
  39.  
  40.     cin >> n >> S;
  41.     a.resize(n);
  42.     for (int i = 0; i < n; i++) cin >> a[i];
  43.  
  44.     auto [k, cost] = maxSouvenirs();
  45.     cout << k << " " << cost << "\n";
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 100
1 2 5 6
stdout
copy 
4 54
https://ideone.com/u7ueEq
language:
C++ (gcc 8.3)
created:
2 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!