提出詳細
ソースコード
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#define FOR(i, a, b) for(int i = (a); i < (b);i++)
#define REP(i,n) for(int i = 0;i < (n);i++)
#define ALL(a) (a).begin() , (a).end()
#define DEBUG(x) cout << #x <<": "<< x <<endl
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
using namespace std;
const long long MAX = 1000000000;
bool check(vector<long long> a, vector<long long> b, long long d, long long c, long long n){
long long i;
long long total = 0;
REP(i, n){
long long t = a[i] - b[i] * d;
if(t <= 0){return false;}
total += (t - 1) / c;
}
return total >= d;
}
void solve(){
long long n,c;
vector<long long> a,b;
vector<long long> num;
cin >> n >> c;
REP(i, n){
long long tem1,tem2;
cin >> tem1 >> tem2;
a.push_back(tem1);
b.push_back(tem2);
}
long long cc;
long long ai,bi;
ai = MAX;
bi = 0;
//DEBUG(ai);
//DEBUG(bi);
while(bi + 1 < ai){
cc = (ai + bi)/2;
//DEBUG(cc);
//DEBUG(check(a, b, cc, c, n));
//DEBUG(ai);
//DEBUG(bi);
if(check(a, b, cc, c, n)){bi = cc;}
else{ai = cc;}
}
cout << bi+1 << endl;
}
int main(void){
int n = 0;
int i = 0;
cin >> n;
REP(i, n){
cout << "Case #" << i + 1 << ":" << endl;
solve();
}
}
提出情報
提出出力結果
テストケース情報