MOVE12 - VOI 2012 Điều động
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<ctype.h>
#define ep 0.00001
#define maxn 10011
#define oo 1111111111
#define modunlo 35000
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);
//#include<conio.h>
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,c[maxn],t[maxn],T;
vector <int> V1,V2;
bool check(int x){
V1.clear();
V2.clear();
for(int i = 0; i < n; i++){
T = x/t[i];
V1.push_back(max(1,c[i]-T));
V2.push_back(min(n,c[i]+T));
}
sort(V1.begin(),V1.end());
sort(V2.begin(),V2.end());
for(int i = 0; i < n; i++){
if(V1[i] > i+1 || V2[i] < i+1) return false;
}
return true;
}
int main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d %d",&c[i],&t[i]);
}
int u = 0, v = oo , r;
while( u < v){
r = (u + v)/2;
if(check(r)) v = r;
else u = r + 1;
}
printf("%d",u);
}