C. Sagheer and Nubian Market
二分k，首先O(n)得到改变后的数组，用优先队列得到前k各最小值，总的时间复杂度是O(nlogn)
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll unsigned long long
#define inf 1000000000LL
#define mod 1000000007
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e5+10;
int a[N],n;
ll sum[N];
ll check(ll k){
priority_queue<ll,vector<ll>,greater<ll> >que;
for(int i=1;i<=n;i++){
ll x=a[i]+i*k;
que.push(x);
}
ll ans=0;
for(int i=1;i<=k;i++){
ans+=que.top();
que.pop();
}
return ans;
}
int main()
{
// while(true)
{
n=read();
int m=read();
for(int i=1;i<=n;i++) a[i]=read();
int l=0,r=n;
ll ans,cans;
ll sd=m;
while(l<=r){
ll mid=(l+r)>>1;
ll tmp=check(mid);
if(tmp<=sd){
l=mid+1;
ans=mid;
cans=tmp;
}
else r=mid-1;
}
printf("%I64d %I64d
",ans,cans);
}
return 0;
}