Submission #2135970

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <math.h>
#include <array>
#include <list>
#include <set>
#define MOD 1000000007
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> p;
typedef vector<int> vi;
typedef vector<ll> vl;
set <int> st;
vector<int> videos(105);
double now=0;
queue<int> num;
ll n,k;
vl w(100005);
vl d(100005);

bool solve(ll left,ll right)
{
  ll mid=(left+right)/2;
  ll cnt=0;
  for(int i=0;i<n;i++)
    {
      if(w[i]<=mid)
	{
	  cnt+=((mid-w[i])/d[i]+1);
	}
    }
  return (cnt>=k);
}
int main(int argc,char const* argv[])
{
  cin >> n >> k;
  for(int i=0;i<n;i++)
    {
      cin >> w[i] >> d[i];
    }
  ll left=-1;
  ll right=LONG_LONG_MAX;
  ll mid;
  while(right-left>1)
    {
      mid=(left+right)/2;
      if(solve(left,right)==true)
	{
	  right=mid;
	}
      else
	{
	  left=mid;
	}
    }
  cout << right << endl;
  return 0;
}

Submission Info

Judge Result