Advertisement
Guest User

Untitled

a guest
Jun 1st, 2017
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <utility>
  5.  
  6. #define mp make_pair
  7. #define pli pair<long long, int>
  8. typedef long long lli;
  9.  
  10. using namespace std;
  11.  
  12. int n, s;
  13. pli arr[100003];
  14. int main(){
  15.     cin >> n >> s;
  16.    
  17.     for(int i = 0; i < n; i++){
  18.         cin >> arr[i].first;
  19.         arr[i].second = i+1;
  20.     }
  21.     int best = 0;
  22.     lli bprice = 0;
  23.     int prevk = 0;
  24.     int lo = 0, hi = n;
  25.     while(lo <= hi){
  26.         int k = (lo+hi)/2;
  27.         for(int i = 0; i < n; i++){
  28.             arr[i].first += arr[i].second*(k-prevk);
  29.         }
  30.         sort(arr, arr+n);
  31.         lli tot = 0;
  32.         for(int i = 0; i < k; i++){
  33.             tot += arr[i].first;
  34.         }
  35.         if(tot > s){
  36.             hi = k-1;
  37.         }else{
  38.             if(k > best){
  39.                 best = k;
  40.                 bprice = tot;
  41.             }
  42.             lo = k+1;
  43.         }
  44.         prevk = k;
  45.     }
  46.     cout << best << " " << bprice << "\n";
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement