## 【CodeForces-812C】Sagheer and Nubian Market【二分】

【CodeForces-812C】Sagheer and Nubian Market【二分】

Solution:

```#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
int w;
struct Node {
int val, id;
bool operator < (const Node & n) const {
return val + id * w < n.val + n.id * w;
}
};

const int LIM = 1e5 + 10;
Node dat[LIM];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
LL s;
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> dat[i].val;
dat[i].id = i + 1;
}
int l = 0, r = n;
int mid;
LL sum;
while (l + 1 < r) {
mid = (l + r) >> 1;
w = mid;
sort(dat, dat + n);
sum = 0;
for (int i = 0; i < mid && sum >= 0; i++)
sum += dat[i].val + dat[i].id * mid;
// cout << mid << ": " << sum << endl;
if (sum >= s || sum < 0) r = mid;
else l = mid;
}
w = l;
sort(dat, dat + n);
LL ansa = 0;
for (int i = 0; i < l; i++)
ansa += dat[i].val + dat[i].id * l;
w = r;
sort(dat, dat + n);
LL ansb = 0;
for (int i = 0; i < r; i++)
ansb += dat[i].val + dat[i].id * r;
if (ansb > s) cout << l << ' ' << ansa;
else cout << r << ' ' << ansb;
cout << '\n';
return 0;
}
```