Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n,c[10100],t[10100],l[10100],r[10100];

int possible(int T)
{
    for (int i=1;i<=n;i++) l[i]=r[i]=0;
    for (int i=0;i<n;i++) l[max(1,c[i]-T/t[i])]++, r[min(n,c[i]+T/t[i])]++;

    for (int i=1;i<=n;i++)
    {
        l[i]+=l[i-1]; r[i]+=r[i-1];
        if (l[i]<i || r[i]>i) return 0;
    }
    return 1;
}

int main()
{
    cin >> n;
    for (int i=0;i<n;i++) cin >> c[i] >> t[i];

    int low=0,high=100000000,ans=high;
    while (low<=high)
    {
        int mid=(low+high)>>1;
        if (possible(mid)) ans=mid, high=mid-1;
        else low=mid+1;
    }
    cout << ans << endl;
}

Code mẫu của happyboy99x

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

Code mẫu của ladpro98

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

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 100111;

int n, x[MN], t[MN];
pair<int,int> a[MN];
multiset< pair<int,int> > s;

bool check(int v) {
    FOR(i,1,n) {
        int can = v / t[i];
        a[i] = MP(max(x[i] - can, 1), min(x[i] + can, n));
    }
    sort(a+1, a+n+1);
    s.clear();

    int j = 0;
    FOR(i,1,n) {
        while (j < n && a[j+1].F <= i) {
            ++j;
            s.insert(MP(a[j].S, a[j].F));
        }
        if (s.empty()) return false;
        pair<int,int> cur = *s.begin(); s.erase(s.begin());

        if (cur.F < i) return false;
    }
    return true;
}

int main() {
    scanf("%d", &n);
    FOR(i,1,n) scanf("%d%d", &x[i], &t[i]);

    int l = 0, r = 1000111000, res = r;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

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

}

Code mẫu của skyvn97

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