fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. bool check(vector<int> &arr,int mid,int m){
  8.  
  9. int n = arr.size();
  10. vector<int> temp(n+1,0);
  11.  
  12. for(int i=1;i<=n;i++){
  13. int a = i*mid + arr[i];
  14. temp[i]=a;
  15. }
  16.  
  17. sort(temp.begin()+1,temp.end());
  18. int sum=0;
  19.  
  20. for(int i=1;i<=mid;i++){
  21. sum+=temp[i];
  22.  
  23. }
  24.  
  25. return sum<=m;
  26.  
  27. }
  28. int main() {
  29. // your code goes here
  30. int n,m;
  31. cin>>n>>m;
  32. vector<int> arr(n+1,0);
  33. int low=0;
  34. int high=n;
  35.  
  36. for(int i=1;i<=n;i++){
  37. cin>>arr[i];
  38. }
  39. int ans=0;
  40.  
  41. while(low<=high){
  42. int mid=(low+high)/2;
  43.  
  44. if(check(arr,mid,m)==true){
  45. ans=mid;
  46. low=mid+1;
  47.  
  48. }
  49. else{
  50. high=mid-1;
  51.  
  52. }
  53. }
  54.  
  55. cout<<ans<<endl;
  56.  
  57.  
  58. return 0;
  59. }
Success #stdin #stdout 0s 544KB
stdin
4 33
4 3 2 1
stdout
3