AcWing 4656. 技能升级
原题链接
困难
作者:
sonic407
,
2023-01-09 21:18:36
,
所有人可见
,
阅读 100
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, m, a[N], b[N];
bool check(int c) {
long long s = 0;
for (int i = 1; i <= n; i ++ ) {
if (a[i] >= c) {
s += (a[i] - c) / b[i] + 1;
}
}
return s >= m;
}
int main() {
scanf("%d%d", &n, &m);
int l = 0, r = 1e6;
for (int i = 1; i <= n; i ++ ) {
scanf("%d%d", &a[i], &b[i]);
}
while (l < r) {
int md = (l + r + 1) / 2;
if (check(md)) {
l = md;
} else {
r = md - 1;
}
}
long long res = 0, s = 0;
for (int i = 1; i <= n; i ++ ) {
if (a[i] >= l) {
int c = (a[i] - l) / b[i] + 1;
int e = a[i] - (c - 1) * b[i];
res += (long long)(a[i] + e) * c / 2;
s += c;
}
}
printf("%lld\n", res - (s - m) * l);
return 0;
}