MOVE12 - VOI 2012 Điều động
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<queue>
#include<vector>
#define MAX 10010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e8+7;
int c[MAX];
int t[MAX];
vector<int> seg[MAX];
int n;
void init(void) {
scanf("%d",&n);
FOR(i,1,n) {
scanf("%d",&c[i]);
scanf("%d",&t[i]);
}
}
bool ok(int x) {
FOR(i,1,n) seg[i].clear();
FOR(i,1,n) {
int ran=x/t[i];
seg[max(1,c[i]-ran)].push_back(min(n,c[i]+ran));
}
priority_queue<int,vector<int>,greater<int> > q;
while (!q.empty()) q.pop();
FOR(i,1,n) {
FORE(it,seg[i]) q.push(*it);
while (!q.empty() && q.top()<i) q.pop();
if (q.empty()) return (false);
q.pop();
}
return (true);
}
void process(void) {
int l=0;
int r=INF;
while (true) {
if (l==r) {
printf("%d",r);
return;
}
if (r-l==1) {
if (ok(l)) printf("%d",l);
else printf("%d",r);
return;
}
int m=(l+r)>>1;
if (ok(m)) r=m;
else l=m+1;
}
}
int main(void) {
init();
process();
return 0;
}