dinhquang070811
Thông tin
#include<bits/stdc++.h>\ using namespace std;\ const int nmax=1e5+5;\ int c[nmax],t[nmax],n,Tmin;\ typedef pair<int,int> II;\ II A[nmax];\ priority_queue<int,vector<int>,greater<int> >q;\ int kiemtra(int x)\ {\ while(!q.empty()) q.pop();\ for(int i=1;i<=n;i++)\ {\ A[i].first=max(1,c[i]-x/t[i]);\ A[i].second=min(n,c[i]+x/t[i]);\ }\ sort(A+1,A+n+1);\ int j=1;\ for(int i=1;i<=n;i++)\ {\ while(j<=n&&A[j].first<=i) q.push(A[j++].second);\ if(q.empty()||q.top()<i) return 0;\ q.pop();\ }\ return 1;\ }\ int main()\ {\ freopen("DIEUDONG.INP","r",stdin);\ freopen("DIEUDONG.OUT","w",stdout);\ cin>>n;\ for(int i=1;i<=n;i++) {cin>>c[i]>>t[i];}\ int l=0,r=10e8,m;\ while(l<=r)\ {\ m=(l+r)/2;\ if(kiemtra(m)){Tmin=m;r=m-1;}\ else l=m+1;\ }\ cout<<Tmin;\ return 0;\ }