MOVE12 - VOI 2012 Điều động
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 10000;
int c[N], t[N], n;
bool ok(int timeLimit) {
vector<pair<int, int> > limit (n);
for(int i = 0; i < n; ++i)
limit[i] = make_pair(max(0, c[i] - timeLimit / t[i]), min(n - 1, c[i] + timeLimit / t[i]));
sort(limit.begin(), limit.end());
priority_queue<int> q;
for(int pos = 0, x = 0; pos < n; ++pos) {
while(x < n && limit[x].first <= pos)
q.push(-limit[x++].second);
if(q.empty() || pos > -q.top()) return false;
q.pop();
}
return true;
}
void enter() {
cin >> n;
for(int i = 0; i < n; ++i)
cin >> c[i] >> t[i], --c[i];
}
void solve() {
int low = 0, high = 1e9;
while(low < high) {
int mid = (low + high) >> 1;
if(ok(mid)) high = mid;
else low = mid + 1;
}
cout << low << '\n';
}
int main() {
ios::sync_with_stdio(false);
enter();
solve();
return 0;
}