MOVE12 - VOI 2012 Điều động

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second

const int N = 10005;
const int oo = trunc(1e9);
using namespace std;
int c[N], t[N];
int n, res;
ii List[N];

void Init(int lim) {
    int Range, Left, Right;
    for(int i=1; i<=n; i++) {
        Range = lim / t[i];
        Left = max(c[i] - Range, 1);
        Right = min(c[i] + Range, n);
        List[i] = ii(Left, Right);
    }
    sort(List + 1, List + 1 + n);
}

bool Slide() {
    int pos = 1, R;
    priority_queue<int, vector<int>, greater<int> > Q;
    for(int i=1; i<=n; i++) {
        while (pos <= n && List[pos].X <= i)
            Q.push(List[pos++].Y);
        if (!Q.size()) return false;
        R = Q.top(); Q.pop();
        if (R < i) return false;
    }
    return true;
}

int main()
{
    scanf("%d\n", &n);
    for(int i=1; i<=n; i++)
        scanf("%d %d\n", &c[i], &t[i]);
    int l = 0, r = oo, m;
    while (l <= r) {
        m = (l + r) >> 1;
        Init(m);
        if (Slide()) {
            res = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    printf("%d", res);
    return 0;
}

Download