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