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);
    
}

Download