-
Notifications
You must be signed in to change notification settings - Fork 0
/
3351.cpp
54 lines (41 loc) · 840 Bytes
/
3351.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100002
#define MAX 2 * 1e18
typedef vector<int> vi;
typedef long long ll;
vi a(MAXN), r(MAXN);
bool reaches_k(int n, ll k, ll t)
{
ll total_views = 0;
for(int i = 0; i < n; i++)
{
total_views += ((t - a[i]) / r[i]) + 1;
if(total_views >= k) return true;
}
return false;
}
ll binary_search(int n, ll k)
{
ll lo = 0, hi = MAX, time = hi;
while(lo <= hi)
{
ll md = (lo + hi) / 2;
if(reaches_k(n, k, md)) hi = md - 1, time = md;
else lo = md + 1;
}
return time;
}
int main()
{
ll n, k;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i] >> r[i];
cout << binary_search(n, k) << endl;
}
/*
an = a1 + (n - 1) * r
(an - a1) / r = (n - 1)
((an - a1) / r) + 1 = n
*/